http://hdu.hustoj.com/showproblem.php?pid=2063
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0
Sample Output
3
Author
PrincessSnow
三种方法（网络流 匈牙利）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 10005 typedef long long ll; using namespace std; int V; int x,y; int k,m,n; vector<int>G[maxn]; int match[maxn]; bool used[maxn]; //向图中增加一条连接u和v的边 void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } //通过dfs寻找增广路 bool dfs(int v) { used[v]=true; for(int i=0;i<G[v].size();i++) { int u=G[v][i]; int w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[v]=u; match[u]=v; return true; } } return false; } int erfen() { int res=0; memset(match,-1,sizeof(match)); for(int i=1;i<=m;i++) { if(match[i]<0) { memset(used,false,sizeof(used)); if(dfs(i)) { res++; } } } return res; } int main() { while(scanf("%d",&k)!=EOF) { if(k==0)break; scanf("%d%d",&m,&n); for(int i=0;i<maxn;i++) { G[i].clear(); } // memset(match,-1,sizeof(match)); for(int i=0;i<k;i++) { cin>>x>>y; add_edge(x,y+m); } int ans=erfen(); printf("%d ",ans); } return 0; } //#include<iostream> //#include<cstdio> //#include<cstring> //#include<cmath> //#include<queue> //#include<set> //#include<algorithm> //#include<map> //#define maxn 200005 //typedef long long ll; //using namespace std; //int V; //int x,y; //int k,m,n; //vector<int>G[maxn]; //int match[maxn]; //bool used[maxn]; ////向图中增加一条连接u和v的边 //void add_edge(int u,int v) //{ // G[u].push_back(v); // //G[v].push_back(u); //} ////通过dfs寻找增广路 //bool dfs(int v) //{ // // for(int i=0;i<G[v].size();i++) // { // int u=G[v][i]; // if(used[u])continue; // used[u]=true; // int w=match[u]; // if(w<0||dfs(w)) // { // //match[v]=u; // match[u]=v; // return true; // } // } // return false; //} //int erfen() //{ // int res=0; // memset(match,-1,sizeof(match)); // for(int i=1;i<=m;i++) // { // memset(used,false,sizeof(used)); // if(dfs(i)) // { // res++; // } // } // return res; //} //int main() //{ // while(scanf("%d",&k)!=EOF) // { // if(k==0)break; // scanf("%d%d",&m,&n); // for(int i=0;i<maxn;i++) // { // G[i].clear(); // } // memset(match,-1,sizeof(match)); // for(int i=0;i<k;i++) // { // cin>>x>>y; // add_edge(x,y); // } // int ans=erfen(); // printf("%d ",ans); // } // return 0; //}
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 2005 typedef long long ll; #define inf 10000009 using namespace std; int n,k; int zzz,x,y; bool can[maxn][maxn];//can[][]表示计算机i能够处理的任务 struct edge{ int to,cap,rev; //边的终点，容量，反向边 }; vector<edge>mp[maxn]; // 邻接图 bool vis[maxn]; void add_edge(int from,int to,int cap) //建图 { mp[from].push_back((edge){to,cap,mp[to].size()}); mp[to].push_back((edge){from,0,mp[from].size()-1}); //反向弧 } int dfs(int v,int t,int f) //找增广路 v，t是最终点 用了f的流量 { if(v==t)return f; vis[v]=true; for(int i=0;i<mp[v].size();i++) { edge &e=mp[v][i]; if(!vis[e.to]&&e.cap>0) { int d=dfs(e.to,t,min(f,e.cap)); //遍历所有的路径 if(d>0) { e.cap-=d; //求增加的流量 mp[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; for(;;) { memset(vis,0,sizeof(vis)); //初始化 int f=dfs(s,t,inf); if(f==0)return flow; flow+=f; } } void solve() { int s=n+k+1; int t=s+1; for(int i=0;i<n;i++) { add_edge(s,i,1); } for(int i=0;i<k;i++) { add_edge(n+i,t,1); } for(int i=0;i<n;i++) { for(int j=0;j<k;j++) { if(can[i][j]==1) { //cout<<i<<" "<<j; add_edge(i,n+j,1); } } } cout<<max_flow(s,t)<<endl; } int main() { while(scanf("%d",&zzz)!=EOF) { if(zzz==0)break; scanf("%d%d",&n,&k); for(int i=0;i<maxn;i++) { mp[i].clear(); } memset(can,0,sizeof(can)); for(int i=0;i<zzz;i++) { cin>>x>>y; x--; y--; can[x][y]=1; } solve(); } return 0; }