匈牙利：
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<iomanip> #include<cstring> using namespace std; typedef long long ll; const int N=4004; int read() { int res=0,ch,flag=0; if((ch=getchar())=='-') //判断正负 flag=1; else if(ch>='0'&&ch<='9') //得到完整的数 res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } int n,m; int result[N],use[N]; int e[N*16],ne[N*16],idx,h[N*16]; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool dfs(int now) { for(int j=h[now]; ~j; j=ne[j]) { int v=e[j]; if(!use[v]) { use[v]++; if(!result[v]||dfs(result[v])) { result[v]=now; return true; } } } return false; } int main() { idx=0; memset(h,-1,sizeof h); m=read(),n=read(); int a,b; a=read(),b=read(); while(a!=-1&&b!=-1) { add(a,b); a=read(),b=read(); } int ans=0; for(int i=1; i<=m; i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } cout<<ans<<endl; for(int i=m+1; i<=n; i++) if(result[i]) cout<<result[i]<<" "<<i<<endl; return 0; }
网络流：
#include <iostream> #include <cstdio> #include <cstring> #define N 100010 using namespace std; int n,m,S,T,tmp1,tmp2,tot; int idx,head[N],h[N],q[N],ans1[N],ans2[N]; int e[N],ne[N],w[N]; bool b[N]; inline void add(int u,int v,int f) { e[idx]=v; w[idx]=f; ne[idx]=head[u]; head[u]=idx++; e[idx]=u; w[idx]=0; ne[idx]=head[v]; head[v]=idx++; } inline bool bfs() { int f=0,t=0; memset(h,-1,sizeof(h)); q[t++]=S; h[S]=0; while(f<t) { int now=q[f++]; for(int i=head[now]; ~i; i=ne[i]) { int v=e[i]; if(h[v]==-1&&w[i]) { h[v]=h[now]+1; q[t++]=v; } } } if(h[T]!=-1) return 1; return 0; } inline int dfs(int x,int f) { if(x==T) return f; int w1,used=0; for(int i=head[x]; ~i; i=ne[i]) { int v=e[i]; if(h[v]==h[x]+1&&w[i]) { w1=dfs(v,min(f-used,w[i])); w[i]-=w1; w[i^1]+=w1; used+=w1; if(used==f) return f; } } if(!used)h[x]=-1; return used; } void dinic() { while(bfs()) tot+=dfs(S,0x3f3f3f3f); } int main() { memset(head,-1,sizeof head); scanf("%d %d",&m,&n); S=0,T=n+1; scanf("%d %d",&tmp1,&tmp2); do { add(tmp1,tmp2,0x3f3f3f3f); scanf("%d %d",&tmp1,&tmp2); }while(tmp1!=-1&&tmp2!=-1); for(int i=1; i<=m; i++) add(S,i,1); for(int i=m+1; i<=n; i++) add(i,T,1); dinic(); if(tot==0) { puts("No Solution!"); return 0; } printf("%d ",tot); for(int i=0; i<idx; i=i+2) { if(e[i]!=S&&e[i^1]!=S) if(e[i]!=T&&e[i^1]!=T) if(w[i^1]!=0) { printf("%d %d ",e[i^1],e[i]); } } return 0; }