题意：有(m)个插座，(n)个电设备，每个插座可以插特定的几个电设备，每个电设备也可以配特定的几个插座，现在又一个插线板可以选择其中的一个插座让它变成(3)个，求最大匹配数
分析：很明显二分图匹配，如果没有插线板，那么匈牙利算法跑一遍就可以了，如果说把每一种插座都插插线板跑二分图，就会超时。
其实可以先不考虑插线板，跑一次二分图，然后对n种插座都插插线板，把插线板插在i插座上，就相当于再找两次增广路，如果能够找到，就在原先匹配上++
AC_Code:
1 #include <iostream> 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=75010; 6 const double inf=9999999999.9; 7 const int mod=1e9+7; 8 #define rep(i,first,second) for(int i=first;i<=second;i++) 9 #define dep(i,first,second) for(int i=first;i>=second;i--) 10 11 int mat[1510],match[1510],in[1510],vis[1510]; 12 vector<int>gra[maxn]; 13 int n,m,k; 14 15 void getMap(){ 16 memset(match,0,sizeof(match)); 17 memset(in,0,sizeof(in)); 18 scanf("%d%d%d",&m,&n,&k); 19 rep(i,1,k){ 20 int u,v; 21 scanf("%d%d",&u,&v); 22 gra[u].push_back(v); 23 in[u]++; 24 } 25 } 26 27 int dfs(int x){ 28 for(int i=0;i<gra[x].size();i++){ 29 int v=gra[x][i]; 30 if(!vis[v]){ 31 vis[v]=1; 32 if( match[v]==0||dfs(match[v])){ 33 match[v]=x; 34 return 1; 35 } 36 } 37 } 38 return 0; 39 } 40 41 42 int Hungray(){ 43 int ans=0; 44 rep(i,1,m){ 45 memset(vis,0,sizeof(vis)); 46 ans+=dfs(i); 47 } 48 return ans; 49 } 50 51 int main() 52 { 53 getMap(); 54 int ans=Hungray(); 55 rep(i,1,n){ 56 mat[i]=match[i];//保存不考虑插线板的时候的匹配情况 57 } 58 int x=0,mmax=0; 59 rep(i,1,n){ 60 if(in[i]>1){ 61 rep(j,1,n) match[j]=mat[j]; 62 rep(j,m+1,m+2){//增加两个 63 gra[j].clear(); 64 for(int q=0;q<gra[i].size();q++){ 65 gra[j].push_back(gra[i][q]); 66 } 67 } 68 x=0; 69 memset(vis,0,sizeof(vis)); 70 x+=dfs(m+1); 71 memset(vis,0,sizeof(vis)); 72 x+=dfs(m+2); 73 mmax=max(mmax,x); 74 if( mmax==2 ) break; 75 } 76 } 77 ans+=mmax; 78 printf("%d ",ans); 79 return 0; 80 }
1 #include <iostream> 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=75010; 6 const double inf=9999999999.9; 7 const int mod=1e9+7; 8 #define rep(i,first,second) for(int i=first;i<=second;i++) 9 #define dep(i,first,second) for(int i=first;i>=second;i--) 10 #define erep(i,u) for(int i=head[u];~i;i=e[i].nxt) 11 12 struct edge{int to,nxt;}e[maxn]; 13 int head[1510],tot; 14 int match[1510],vis[1510],mat[1510]; 15 int n,m,k; 16 17 void add(int u,int v){ 18 e[tot].to=v; 19 e[tot].nxt=head[u]; 20 head[u]=tot++; 21 } 22 23 int dfs(int u){ 24 erep(i,u){ 25 int v=e[i].to; 26 if( !vis[v] ){ 27 vis[v]=1; 28 if( match[v]==0 || dfs(match[v])){ 29 match[v]=u; 30 return 1; 31 } 32 } 33 } 34 return 0; 35 } 36 37 int Hungray(){ 38 int ans=0; 39 rep(i,1,m){ 40 memset(vis,0,sizeof(vis)); 41 ans+=dfs(i); 42 } 43 return ans; 44 } 45 46 void init(){ 47 tot=0; 48 memset(head,-1,sizeof(head)); 49 memset(match,0,sizeof(match)); 50 } 51 52 int main() 53 { 54 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 55 init(); 56 scanf("%d%d%d",&m,&n,&k); 57 rep(i,1,k){ 58 int u,v; 59 scanf("%d%d",&u,&v); 60 add(u,v); 61 } 62 int ans=Hungray(); 63 64 rep(i,1,n) mat[i]=match[i]; 65 int x=0,maxx=0; 66 rep(i,1,m){ //注意与邻接矩阵的不同之处(还不知道为什么) 67 rep(j,1,n) match[j]=mat[j]; 68 x=0; 69 rep(j,1,2){ 70 memset(vis,0,sizeof(vis)); 71 if( dfs(i) ) x++; 72 else break; 73 } 74 maxx=max(maxx,x); 75 } 76 ans+=maxx; 77 printf("%d ",ans); 78 return 0; 79 }