Ural 1277 cops ans thieves （最小割模型）

本文主要是介绍Ural 1277 cops ans thieves （最小割模型），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    题目地址 ：http://acm.timus.ru/problem.aspx?space=1&num=1277

这里我们要拆点。把一个点拆成i,i' 。如何 i，j有边 ，在建边(i,j',inf),(j,i',inf)。 然后每个点点边(i',i,R[i])。这样建边以后，若要阻止 s到f的路径，那么必须破败一些边，那么我们为了是的边权最小，必须破坏边权小于inf的边，对应的就是图中拆点后的边(j’->j)  。实际上 这条边就代表了点j的点权。求最小割即是答案。 有一个需要注意的地方那个s==f的时候要特判。

VIEW CODE  

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int mmax= 210;
const int mod=1000000007;
const int inf=0x3fffffff;
using namespace std;struct node
{int flow;int en;int next;
}E[40010+mmax];
int p[mmax];
int num;
void init()
{memset(p,-1,sizeof p);num=0;
}
void add(int st,int en,int flow)
{E[num].en=en;E[num].flow=flow;E[num].next=p[st];p[st]=num++;E[num].en=st;E[num].flow=0;E[num].next=p[en];p[en]=num++;
}int d[mmax];
bool vis[mmax];
int qq[mmax];
int cur[mmax];
bool bfs(int st,int en)
{memset(vis,0,sizeof vis);int qcnt=0;qq[++qcnt]=st;d[st]=0;vis[st]=1;while(qcnt){int x=qq[qcnt];qcnt--;for(int i=p[x]; i+1; i=E[i].next){int v=E[i].en;if(!vis[v]&&E[i].flow){vis[v]=1;qq[++qcnt]=v;d[v]=d[x]+1;}}}return vis[en];
}
int dfs(int st,int en,int  flow)
{if(st==en||flow==0)return flow;int f=0,dd;for(int &i=cur[st]; i+1;i=E[i].next){int v=E[i].en;if(d[st]+1==d[v]&&(dd=dfs(v,en,min(flow,E[i].flow)))>0){E[i].flow-=dd;E[i^1].flow+=dd;flow-=dd;f+=dd;if(flow==0)break;}}return f;
}
int dinic(int st,int en,int n)
{int flow=0;while(bfs(st,en)){for(int i=0;i<=n;i++)cur[i]=p[i];flow+=dfs(st,en,inf);}return flow;
}int main()
{int k,n,m,s,f;while(cin>>k){init();scanf("%d %d %d %d",&n,&m,&s,&f);for(int i=1;i<=n;i++){int x;scanf("%d",&x);add(n+i,i,x);}for(int i=0;i<m;i++){int u,v;scanf("%d %d",&u,&v);add(u,v+n,inf);add(v,u+n,inf);}if(s==f){puts("NO");continue;}int ans=dinic(s,f+n,2*n);if(ans<=k)puts("YES");elseputs("NO");}return 0;
}

这篇关于Ural 1277 cops ans thieves （最小割模型）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---