POJ-1149 参考大牛的构图..

POJ-1149 参考大牛的构图..

自己开始构图..各种奇葩..各种bug不对...实在不行了...还是看了大牛的构图:

​​          对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。           对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为 +∞。          从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

对大牛真是五体投地..网络流不会构图就相当于不会网络流..但构图又都是如此的巧妙..我怎样才能想到....

看大牛对这题的构图,开始是从一个具体的直观比较复杂的图..经过一步步简化成抽象但简单的图...这种思维~~学习啊...

Program:

#include#include#include#include#include#define oo 2000000000using namespace std;struct node{ int x,y,c,next;}line[50005];int m,n,M,_link[2005],ans,dis[2005],num,way[2005];queue myqueue;bool BFS(){ int h,k; while (!myqueue.empty()) myqueue.pop(); memset(dis,0,sizeof(dis)); dis[0]=1; 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[line[k].y]=dis[h]+1; myqueue.push(line[k].y); } k=line[k].next; } } return dis[n];}bool DFS(int p,int Flow){ int k; if (p==n) { ans+=Flow; for (k=1;k<=num;k++) { line[way[k]].c-=Flow; m++; line[m].x=line[way[k]].y; line[m].y=line[way[k]].x; line[m].c=Flow; line[m].next=_link[line[m].x]; _link[line[m].x]=m; } return true; } k=_link[p]; num++; while (k) { if (line[k].c && dis[line[k].y]-dis[p]==1) { way[num]=k; if (DFS(line[k].y,min(Flow,line[k].c))) return true; } k=line[k].next; } num--; return false;}void MaxFlow(){ ans=0; while (BFS()) { num=0; DFS(0,oo); }} int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,k,h,j,need,sum[1005],who[1005]; memset(_link,0,sizeof(_link)); scanf("%d%d",&M,&n); for (i=1;i<=M;i++) scanf("%d",&sum[i]); memset(who,0,sizeof(who)); for (i=1;i<=n;i++) { scanf("%d",&k); for (j=1;j<=k;j++) { scanf("%d",&h); if (!who[h]) { who[h]=i; m++; line[m].x=0; line[m].y=i; line[m].c=sum[h]; line[m].next=_link[line[m].x]; _link[line[m].x]=m; }else { m++; line[m].x=who[h]; line[m].y=i; line[m].c=oo; line[m].next=_link[line[m].x]; _link[line[m].x]=m; } } scanf("%d",&need); m++; line[m].x=i; line[m].y=n+1; line[m].c=need; line[m].next=_link[line[m].x]; _link[line[m].x]=m; } n++; MaxFlow(); printf("%d\n",ans); return 0;}

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