题目地址 ：?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;}
接受失败等于回归真实的自我，接受失败等于打破完美的面具，
