USACO Section 4.2 The Perfect Stall - 网络流求最大二分图匹配..

用网络流求二分图匹配的方法在算法导论上就看到过了..只是一直没去实现..确实用网络流来解二分图匹配有点大材小用了..一般的求最大匹配用匈牙利算法轻轻松松一分钟啊..但是网络流的解法虽然写起来多..但思想也是很简单的...对二分图左边加一个超级源点...超级源点对左边所有点做一条容量为1的边..右边给个超级汇点..右边所有点对超级汇点做一条容量为1的边..而左边所有点的点按照所给的关系对右边做边..容量都为1...这里注意题目给的左边点标号为1~N..右边点为1~M.为了区分左右点..可以将右边点标号看成N+1~N+M...

构好图后跑一遍从超级源点到超级汇点的最大流就是结果了...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: stall4 */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node { int x,y,c,next; }line[10001]; int n,m,MaxFlow,_link[501],way[501],dis[501],dep; bool used[501],f; queue<int> myqueue; bool BFS() { int i,h,k; while (!myqueue.empty()) myqueue.pop(); memset(used,false,sizeof(used)); for (i=0;i<=n;i++) dis[i]=oo; dis[0]=0; myqueue.push(0); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); k=_link[h]; while (k) { if (line[k].c && dis[line[k].y]>dis[h]+1) { dis[line[k].y]=dis[h]+1; if (!used[line[k].y]) { myqueue.push(line[k].y); used[line[k].y]=true; } } k=line[k].next; } } return dis[n]!=oo; } void DFS(int p) { int i,k; if (p==n) { for (i=1;i<=dep;i++) { m++; line[m].x=line[way[i]].y; line[m].y=line[way[i]].x; line[m].c=1; line[m].next=_link[line[m].x]; _link[line[m].x]=m; line[way[i]].c=0; } MaxFlow++; f=true; return; } k=_link[p]; used[p]=true; while (k) { if (!used[line[k].y] && line[k].c && dis[line[k].y]-dis[line[k].x]==1) { way[++dep]=k; DFS(line[k].y); dep--; if (f) return; } k=line[k].next; } used[p]=false; return; } void Dinic() { MaxFlow=0; while (BFS()) { memset(used,false,sizeof(used)); dep=0; f=false; DFS(0); } } int main() { freopen("stall4.in","r",stdin); freopen("stall4.out","w",stdout); scanf("%d%d",&n,&m); int i,x,y,num; memset(_link,0,sizeof(_link)); num=0; for (x=1;x<=n;x++) { scanf("%d",&i); while (i--) { num++; scanf("%d",&y); y+=n; line[num].x=x; line[num].y=y; line[num].c=1; line[num].next=_link[x]; _link[x]=num; } } for (y=1;y<=n;y++) { num++; line[num].x=0; line[num].y=y; line[num].c=1; line[num].next=_link[0]; _link[0]=num; } for (x=n+1;x<=n+m;x++) { num++; line[num].x=x; line[num].y=n+m+1; line[num].c=1; line[num].next=_link[x]; _link[x]=num; } n=m+n+1; m=num; Dinic(); printf("%d\n",MaxFlow); return 0; }