题意：有m个插座，n个电器，每个插座最多可连接一个电器。另外有一个插头，可以使得一个插座连接三个电器，问最大匹配数是多少。
分析：先跑一遍最大匹配，在最大匹配的基础上对每个点找是否还存在增广路即可。
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #include<vector> #include<map> #include<set> #include<queue> //#define _for(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; double eps=1e-10; ll mod=1e15+7; const int INF =0x3f3f3f; const int MAXN=2e3+10; const int maxn = 1e5+10; //ll inf=100000000000000; //template<typename T>inline void read(T &x) //{ // x=0; // static int p;p=1; // static char c;c=getchar(); // while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} // while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} // x*=p; //} typedef unsigned long long ull; const int N=1e5+7; int head[N],match[N],vis[N],tmp[N]; struct Edge{ int u,v,nxt; Edge(int u=0,int v=0,int nxt=0):u(u),v(v),nxt(nxt){} }e[N*30]; int cnt; void add(int u,int v){ e[cnt]=Edge(u,v,head[u]); head[u]=cnt++; } bool dfs(int u){ for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if(vis[v])continue; vis[v]=1; if(match[v]==-1||dfs(match[v])){ match[v]=u; return true; } } return false; } int n,m,k; int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&m,&k); int u,v; cnt=0; for(int i=1;i<=k;i++){ scanf("%d%d",&u,&v); add(u,v); } int ans=0; memset(match,-1,sizeof(match)); for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } memcpy(tmp,match,sizeof(match)); int ans1=0; for(int i=1;i<=n;i++){ int num=0; for(int j=1;j<=2;j++){ memset(vis,0,sizeof(vis)); if(dfs(i))num++; else break; } ans1=max(ans1,num); memcpy(match,tmp,sizeof(tmp)); } printf("%d ",ans+ans1); return 0; }