二分图最大匹配 网络流&匈牙利

时间:2020-12-03 06:08:51

先复习一下dinic

二分图最大匹配 网络流&匈牙利二分图最大匹配 网络流&匈牙利
  1 #include<cstdio> 
  2 #include<cstring>
  3 #include<cmath>
  4 #include<ctime>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<set>
  9 #define inf (0x7fffffff)
 10 #define maxint (2147483647)
 11 #define l(a) ((a)<<1)
 12 #define r(a) ((a)<<1|1)
 13 #define b(a) (1<<(a))
 14 #define rep(i,a,b) for(int i=a;i<=(b);i++)
 15 #define clr(a) memset(a,0,sizeof(a))
 16 typedef long long ll;
 17 using namespace std;
 18 int readint(){
 19     int t=0,f=1;char c=getchar();
 20     while(!isdigit(c)){
 21         if(c=='-') f=-1;
 22         c=getchar();
 23     }
 24     while(isdigit(c)){
 25         t=(t<<3)+(t<<1)+c-'0';
 26         c=getchar();
 27     }
 28     return t*f;
 29 }
 30 ll readll(){
 31     ll t=0ll,f=1ll;char c=getchar();
 32     while(!isdigit(c)){
 33         if(c=='-') f=-1ll;
 34         c=getchar();
 35     }
 36     while(isdigit(c)){
 37         t=(t<<3ll)+(t<<1ll)+ll(c-'0');
 38         c=getchar();
 39     }
 40     return t*f;
 41 }
 42 const int maxn=5009,maxe=1000009;
 43 int n,m,en,S,T,ans,d[maxn];
 44 struct edge{
 45     int v,w;
 46     edge*next,*r;
 47     inline edge(int V,int W){
 48         v=V;w=W;
 49     }
 50     inline edge(){};
 51 }E[maxe],*pt=E,*fir[maxn],*cur[maxn];
 52 void add(int u,int v,int w){
 53     pt->v=v;pt->w=w;
 54     pt->next=fir[u];fir[u]=pt++;
 55 }
 56 void addedge(int u,int v,int w){
 57     add(u,v,w);add(v,u,0);
 58     fir[u]->r=fir[v];fir[v]->r=fir[u];
 59 }
 60 bool Bfs(){
 61     rep(i,S,T) d[i]=0;
 62     queue<int>Q;Q.push(S);d[S]=1;
 63     while(!Q.empty()){
 64         int x=Q.front();Q.pop();
 65         for(edge*e=fir[x];e;e=e->next) if(e->w&&!d[e->v]){
 66             d[e->v]=d[x]+1;Q.push(e->v);
 67         }
 68     }
 69     return d[T];
 70 }
 71 int Dfs(int x,int f){
 72     if(x==T||!f) return f;
 73     int t=0;
 74     for(edge*&e=cur[x];e;e=e->next) if(e->w&&d[e->v]==d[x]+1){
 75         int g=Dfs(e->v,min(f,e->w));
 76         if(g){
 77             e->w-=g;e->r->w+=g;
 78             t+=g;f-=g;
 79             if(!f) break;
 80         }
 81     }
 82     return t;
 83 }
 84 void Dinic(){
 85     while(Bfs()){
 86         rep(i,S,T) cur[i]=fir[i];
 87         ans+=Dfs(S,inf);
 88     }
 89 }
 90 int main(){
 91     //freopen("#input.txt","r",stdin);
 92     //freopen("#output.txt","w",stdout);
 93     n=readint();m=readint();en=readint();S=0;T=n+m+1;
 94     rep(i,1,en){
 95         int U=readint(),V=readint();
 96         if(V>m) continue;
 97         addedge(U,n+V,1);
 98     }
 99     rep(i,1,n) addedge(S,i,1);
100     rep(i,1,m) addedge(n+i,T,1);
101     Dinic();
102     cout<<ans<<endl;
103     //fclose(stdin);
104     //fclose(stdout);
105     return 0;
106 }
dinic

匈牙利 但是似乎姿势不是很对...在洛谷和uoj上都没有dinic快...然而似乎dinic为m根号n..那就可以解释了

BFS 这里用了邻接表

二分图最大匹配 网络流&匈牙利二分图最大匹配 网络流&匈牙利
 1 #include<cstdio> 
 2 #include<cstring>
 3 #include<cmath>
 4 #include<ctime>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<set>
 9 #define maxint (2147483647)
10 #define l(a) ((a)<<1)
11 #define r(a) ((a)<<1|1)
12 #define b(a) (1<<(a))
13 #define mod1 (10000007)
14 #define mod2 (10000009)
15 #define rep(i,a,b) for(int i=a;i<=(b);i++)
16 #define clr(a) memset(a,0,sizeof(a))
17 typedef long long ll;
18 typedef unsigned long long ull;
19 using namespace std;
20 int readint(){
21     int t=0,f=1;char c=getchar();
22     while(!isdigit(c)){
23         if(c=='-') f=-1;
24         c=getchar();
25     }
26     while(isdigit(c)){
27         t=(t<<3)+(t<<1)+c-'0';
28         c=getchar();
29     }
30     return t*f;
31 }
32 const int maxn=2009,maxe=1000009;
33 struct edge{
34     int v;
35     edge*next;
36 }E[maxe],*pt=E,*fir[maxn];
37 void add(int u,int v){
38     pt->v=v;pt->next=fir[u];fir[u]=pt++;
39 }
40 void addedge(int u,int v){
41     add(u,v);add(v,u);
42 }
43 int n,m,en,ans,p[maxn],pre[maxn];
44 bool inq[maxn];
45 void Bfs(int t){
46     queue<int>Q;Q.push(t);clr(inq);
47     int f=-1;inq[t]=1;pre[t]=-1;
48     while(!Q.empty()&&f==-1){
49         int x=Q.front();Q.pop();
50         for(edge*e=fir[x];e;e=e->next){
51             if(!p[e->v]){
52                 ans++;f=1;
53                 int j=e->v,tmp;
54                 for(int i=x;i!=-1;i=pre[i]){
55                     tmp=p[i];p[i]=j;p[j]=i;j=tmp;
56                 }
57                 break;
58             }
59             if(p[e->v]!=-1&&!inq[p[e->v]]){
60                 Q.push(p[e->v]);pre[p[e->v]]=x;inq[p[e->v]]=1;
61             }
62         }
63     }
64     if(f==-1) p[t]=-1;
65 }
66 void Hun(){
67     rep(i,1,n) if(!p[i]) Bfs(i);
68     cout<<ans<<endl;
69     /*rep(i,1,n){
70         printf("%d",p[i]!=-1&&p[i]!=0?p[i]-n:0);
71         putchar(i==n?'\n':' ');
72     }*/
73 }
74 void init(){
75     n=readint();m=readint();en=readint();
76     while(en--){
77         int U=readint(),V=readint();
78         if(V>m) continue;
79         addedge(U,n+V);
80     }
81 }
82 int main(){
83     //freopen("#input.txt","r",stdin);
84     //freopen("#output.txt","w",stdout);
85     init();
86     Hun();
87     //fclose(stdin);
88     //fclose(stdout);
89     return 0;
90 }
匈牙利

邻接矩阵  终于比dinic快了..邻接矩阵大法好

二分图最大匹配 网络流&匈牙利二分图最大匹配 网络流&匈牙利
 1 #include<cstdio> 
 2 #include<cstring>
 3 #include<cmath>
 4 #include<ctime>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<set>
 9 #define maxint (2147483647)
10 #define l(a) ((a)<<1)
11 #define r(a) ((a)<<1|1)
12 #define b(a) (1<<(a))
13 #define mod1 (10000007)
14 #define mod2 (10000009)
15 #define rep(i,a,b) for(int i=a;i<=(b);i++)
16 #define clr(a) memset(a,0,sizeof(a))
17 typedef long long ll;
18 typedef unsigned long long ull;
19 using namespace std;
20 int readint(){
21     int t=0,f=1;char c=getchar();
22     while(!isdigit(c)){
23         if(c=='-') f=-1;
24         c=getchar();
25     }
26     while(isdigit(c)){
27         t=(t<<3)+(t<<1)+c-'0';
28         c=getchar();
29     }
30     return t*f;
31 }
32 const int maxn=4009;
33 int n,m,en,ans,w[maxn][maxn],p[maxn],pre[maxn];
34 bool c[maxn];
35 int Bfs(int S){
36     queue<int>Q;Q.push(S);
37     clr(c);c[S]=1;pre[S]=0;
38     while(!Q.empty()){
39         int x=Q.front();Q.pop();//cout<<"x=="<<x<<endl;
40         rep(i,n+1,n+m) if(w[x][i]){
41             if(!p[i]){
42                 ans++;
43                 int v=i,tmp;
44                 for(int u=x;u;u=pre[u]){
45                     tmp=p[u];p[u]=v;p[v]=u;v=tmp;
46                 }
47                 return 1;
48             }
49             if(p[i]!=-1&&!c[p[i]]){
50                 pre[p[i]]=x;c[p[i]]=1;Q.push(p[i]);
51             }
52         }
53     }
54     return -1; 
55 }
56 void Hun(){
57     int t;
58     rep(i,1,n) if(!p[i]){
59         t=Bfs(i);
60         if(t==-1) p[i]=-1;    
61     }
62     cout<<ans<<endl;
63     rep(i,1,n){
64         printf("%d",p[i]!=-1?p[i]-n:0);
65         putchar(i==n?'\n':' ');
66     }
67 }
68 void init(){
69     n=readint();m=readint();en=readint();
70     while(en--){
71         int U=readint(),V=readint();
72         if(V>m) continue;
73         w[U][n+V]=1;
74     }
75 }
76 int main(){
77     //freopen("#input.txt","r",stdin);
78     //freopen("#output.txt","w",stdout);
79     init();
80     Hun();
81     //fclose(stdin);
82     //fclose(stdout);
83     return 0;
84 }
BFS

DFS 邻接矩阵

二分图最大匹配 网络流&匈牙利二分图最大匹配 网络流&匈牙利
 1 #include<cstdio> 
 2 #include<cstring>
 3 #include<cmath>
 4 #include<ctime>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<set>
 9 #define maxint (2147483647)
10 #define l(a) ((a)<<1)
11 #define r(a) ((a)<<1|1)
12 #define b(a) (1<<(a))
13 #define mod1 (10000007)
14 #define mod2 (10000009)
15 #define rep(i,a,b) for(int i=a;i<=(b);i++)
16 #define clr(a) memset(a,0,sizeof(a))
17 typedef long long ll;
18 typedef unsigned long long ull;
19 using namespace std;
20 int readint(){
21     int t=0,f=1;char c=getchar();
22     while(!isdigit(c)){
23         if(c=='-') f=-1;
24         c=getchar();
25     }
26     while(isdigit(c)){
27         t=(t<<3)+(t<<1)+c-'0';
28         c=getchar();
29     }
30     return t*f;
31 }
32 const int maxn=1009;
33 int n,m,en,ans,w[maxn][maxn],p[maxn],pre[maxn];
34 bool c[maxn];
35 int Dfs(int x){
36     int f=0;//cout<<"x=="<<x<<endl;
37     rep(i,n+1,n+m) if(w[x][i]){
38         if(!p[i]){
39             ans++;
40             int v=i,tmp;
41             for(int u=x;u;u=pre[u]){
42                 tmp=p[u];p[u]=v;p[v]=u;v=tmp;
43             }
44             return 1;
45         }
46         if(p[i]!=-1&&!c[p[i]]){
47             c[p[i]]=1;pre[p[i]]=x;
48             f|=Dfs(p[i]);
49             if(f) return 1;
50         }
51     }
52     return 0;
53 }
54 void Hun(){
55     int t;
56     rep(i,1,n) if(!p[i]){
57         clr(c);pre[i]=0;t=Dfs(i);
58         if(!t) p[i]=-1;
59     }
60     cout<<ans<<endl;
61     rep(i,1,n){
62         printf("%d",p[i]!=-1?p[i]-n:0);
63         putchar(i==n?'\n':' ');
64     }
65 }
66 void init(){
67     n=readint();m=readint();en=readint();
68     while(en--){
69         int U=readint(),V=readint();
70         if(V>m) continue;
71         w[U][n+V]=1;
72     }
73 }
74 int main(){
75     //freopen("#input.txt","r",stdin);
76     //freopen("#output.txt","w",stdout);
77     init();
78     Hun();
79     //fclose(stdin);
80     //fclose(stdout);
81     return 0;
82 }
DFS