ZOJ 2587 - Unique Attack 最小割,判断割边集是否唯一

网友投稿 374 2022-09-14

ZOJ 2587 - Unique Attack 最小割,判断割边集是否唯一

题意:

给了一个无向图以及起点和终点..问最小割边集是否唯一...

题解:

先跑最大流求最小割..然后从起点开始dfs..对能到达的点标记为1(边的容量非空才能走)...再从终点开始dfs...对能到达的点标记为2(对应的边容量非空才能走)..然后扫描所有的边..若一条边已经满流了..但是其起点或者终点没有被标记到.则说明最小割边集不唯一....

Program:

#include #include #include #include #include #include #include #include #define MAXN 905 #define MAXM 50005 #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=c,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

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

上一篇:文案君：杰士邦把玻尿酸用在套套上了，真行！
下一篇:Codeforces 268 B - Two Sets 搜索...
相关文章

 发表评论

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