POJ-2135 自己构图WA了..参考了别人的构图..

看到这题我想到的是以前USACO做的一道构图求最小割的~~构图构得蛮Happy~~猛然发现是无向图..就各种坑爹纠结了...最后跑出样例~~提交还是WA了...呃~~

参考了别人的构图...学习学习..

"基础最小费用最大流。加一个源点S和一个汇点T，源点S与点1连一条容量为2费用为0点边，点n与汇点T也连一条容量为2费用为0的边，对于题目给定的那些边。每条边的容量为1，费用为每条边花费的时间。注意这是双向边。然后求最小费用。"---​

Discuss里有人说跑两次SPFA..其实本题用最小费用最大流的方法就是跑了两次SPFA...本质上是一样的...

解网络流几种形式的方法是基本固定的..像这道题..最后重新构图时,除了main函数里的一些关于构图的代码...其他一点没改..一下子就改好了...所以.网络流的根本还是巧妙的构图...

Program:

#include#include#include#include#define oo 2000000000using namespace std;struct node1{ int x,y,c,w,next;}line[50005];struct node2{ int w,pre,l;}dp[3005];int n,m,_link[3005],ans;bool inqueue[3005];queue myqueue;bool SPFA(){ int i,h,k; memset(dp,-1,sizeof(dp)); memset(inqueue,false,sizeof(inqueue)); while (!myqueue.empty()) myqueue.pop(); myqueue.push(0); dp[0].pre=dp[0].w=0; while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); inqueue[h]=false; k=_link[h]; while (k) { if (line[k].c && (dp[line[k].y].w>dp[h].w+line[k].w || dp[line[k].y].pre==-1)) { dp[line[k].y].w=dp[h].w+line[k].w; dp[line[k].y].pre=h; dp[line[k].y].l=k; if (!inqueue[line[k].y]) { myqueue.push(line[k].y); inqueue[line[k].y]=true; } } k=line[k].next; } } if (dp[n].pre==-1) return false; return true;}void MinCostOfMaxFlow(){ int i; ans=0; while (SPFA()) { i=n; while (i) { line[dp[i].l].c-=1; ans+=line[dp[i].l].w; m++; line[m].x=line[dp[i].l].y; line[m].y=line[dp[i].l].x; line[m].w=-line[dp[i].l].w; line[m].c=1; line[m].next=_link[line[m].x]; _link[line[m].x]=m; i=dp[i].pre; } } return;}int main(){ int p,x,y,w; memset(_link,0,sizeof(_link)); scanf("%d%d",&n,&p); m=0; while (p--) { m++; scanf("%d%d%d",&x,&y,&w); line[m].c=1; line[m].w=w; line[m].x=x; line[m].y=y; line[m].next=_link[line[m].x]; _link[line[m].x]=m; m++; line[m].c=1; line[m].w=w; line[m].x=y; line[m].y=x; line[m].next=_link[line[m].x]; _link[line[m].x]=m; } n++; m++; line[m].x=0; line[m].y=1; line[m].c=2; line[m].w=0; line[m].next=_link[line[m].x]; _link[line[m].x]=m; m++; line[m].x=n-1; line[m].y=n; line[m].c=2; line[m].w=0; line[m].next=_link[line[m].x]; _link[line[m].x]=m; MinCostOfMaxFlow(); printf("%d\n",ans); return 0;}

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