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

网友投稿 292 2022-11-14

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 #include #include #include #include #include#include#include #include #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 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; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：网络
上一篇:USACO Section 5.1 Musical Themes - 题目转换以及KMP..
下一篇:PLC可视化如何实现
相关文章

 发表评论

暂时没有评论，来抢沙发吧~