HDOJ 2435 - There is a war 枚举+最小割

发布时间:2016-12-6 16:12:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 2435 - There is a war 枚举+最小割",主要涉及到HDOJ 2435 - There is a war 枚举+最小割方面的内容,对于HDOJ 2435 - There is a war 枚举+最小割感兴趣的同学可以参考一下。

               题意:                         现在Country one在1号点...Country Another在n号点...CA不想让CO到达自己..所以花费一些代价来砍掉边..并且CA非常的聪明..会选择最小的代价把满足让CO过不来...而CO可以建造一条边或者修善一条边(顶点为2~n-1)..让该边变为不能摧毁..问CA所需要花费的最大代价让CO过不来...                题解:                         先跑最大流.. 求出最小割记为ans1..现在图被割边分成了起点可达与起点不可达两个部分...那么枚举这两个部分的点做边..继续做最大流..注意的是是每次恢复到第一次跑最大流后的状态再加边跑最大流求增加的最小割.其中的最大值记为ans2...那么答案就是ans1+ans2... Program: #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<time.h> #include<map> #include<math.h> #include<queue> #define MAXN 305 #define MAXM 500000 #define oo 1000000007 #define ll long long using namespace std; struct Dinic { struct node { int c,u,v,next; }edge[MAXM]; int ne,head[MAXN]; int cur[MAXN], ps[MAXN], dep[MAXN]; void initial() { ne=2; memset(head,0,sizeof(head)); } void addedge(int u, int v,int c) { edge[ne].u=u,edge[ne].v=v,edge[ne].c=c,edge[ne].next=head[u]; head[u]=ne++; edge[ne].u=v,edge[ne].v=u,edge[ne].c=0,edge[ne].next=head[v]; head[v]=ne++; } int MaxFlow(int s,int t) { int tr, res = 0; int i,j,k,f,r,top; while(1) { memset(dep, -1, sizeof(dep)); for(f=dep[ps[0]=s]=0,r=1;f!= r;) for(i=ps[f++],j=head[i];j;j=edge[j].next) if(edge[j].c&&dep[k=edge[j].v]==-1) { dep[k]=dep[i]+1; ps[r++]=k; if(k == t){ f=r; break; } } if(dep[t]==-1) break; memcpy(cur,head,sizeof(cur)); i=s,top=0; while(1) { if(i==t) { for(tr=oo,k=0;k<top;k++) if(edge[ps[k]].c<tr) tr=edge[ps[f=k]].c; for(k=0;k<top;k++) { edge[ps[k]].c-=tr; edge[ps[k]^1].c+=tr; } i=edge[ps[top=f]].u; res+= tr; } for(j=cur[i];cur[i];j=cur[i]=edge[cur[i]].next) if(edge[j].c && dep[i]+1==dep[edge[j].v]) break; if(cur[i]) ps[top++]=cur[i],i=edge[cur[i]].v; else { if(!top) break; dep[i]=-1; i=edge[ps[--top]].u; } } } return res; } bool mark[MAXN]; void dfs(int u) { mark[u]=true; for (int k=head[u];k;k=edge[k].next) if (!mark[edge[k].v] && edge[k].c) dfs(edge[k].v); } node tempE[MAXM]; int tempH[MAXN],num1,num2,P1[MAXN],P2[MAXN],ans,ans1,x; int getans(int s,int e) { int i,j,Ln; ans=ans1=MaxFlow(s,e); memset(mark,false,sizeof(mark)); dfs(s); Ln=ne; for (x=0;x<=ne;x++) tempE[x]=edge[x]; for (x=0;x<=e;x++) tempH[x]=head[x]; num1=num2=0; for (i=2;i<e;i++) if (mark[i]) P1[++num1]=i; else P2[++num2]=i; for (i=1;i<=num1;i++) for (j=1;j<=num2;j++) { ne=Ln; for (x=0;x<=ne;x++) edge[x]=tempE[x]; for (x=0;x<=e;x++) head[x]=tempH[x]; addedge(P1[i],P2[j],oo); ans=max(ans,ans1+MaxFlow(s,e)); } return ans; } }T; int main() { int C,cases,n,m,s,e,u,v,c; scanf("%d",&C); for (cases=1;cases<=C;cases++) { scanf("%d%d",&n,&m); s=1,e=n,T.initial(); while (m--) { scanf("%d%d%d",&u,&v,&c); T.addedge(u,v,c); } printf("%d\n",T.getans(s,e)); } return 0; }

上一篇:poj 1631 Bridging signals 最长上升子序列的O(n*lgn)方法
下一篇:配置文件实现旋转

相关文章

相关评论