Input There are several test cases.
The first line of a single test case contains two integer N and M ( 2 <= N <= 200; 1 <= M <= 20000), the number of cities and the number of highways. Cities are numbered from 1 to N.
The second line contains two integer S,D ( 1 <= S,D <= N), the number of the source and the number of the destination.
The following N lines contains costs. Of these lines the ith one contains exactly one integer, the cost of locating SA in the ith city to put it under observation. You may assume that the cost is positive and not exceeding 10 7.
The followingM lines tells you about highway network. Each of these lines contains two integers A and B, indicating a bidirectional highway between A and B.
Please process until EOF (End Of File).
Output For each test case you should output exactly one line, containing one integer, the sum of cost of your selected set.
See samples for detailed information.Sample Input
5 6 5 3 5 2 3 4 12 1 5 5 4 2 3 2 4 4 3 2 1
Sample Output
3
题意：
在图中，删除点需要相应的花费，求最小的花费，使得s,t不连通。
思路：
最大流=最小割。
一开始忘记了，这个，想了半天费用流。。。
拆带限制点的流量即可。
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #define fuck(x) cerr<<#x<<" = "<<x<<endl; #define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl; #define ls (t<<1) #define rs ((t<<1)|1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 4008; const int maxm = 200086; const int inf = 0x3f3f3f3f; const ll Inf = 999999999999999999; const int mod = 1000000007; const double eps = 1e-6; const double pi = acos(-1); int Head[maxn],cnt; struct edge{ int Next,v; int w; }e[maxm]; void add_edge(int u,int v,int w){ e[cnt].Next=Head[u]; e[cnt].v=v; e[cnt].w=w; Head[u]=cnt++; } int D_vis[maxn],D_num[maxn]; int source,meeting; int n,m; bool bfs() { memset(D_vis,0,sizeof(D_vis)); for(int i=0;i<=2*n;i++){//注意要覆盖所有点 D_num[i]=Head[i]; } D_vis[source]=1; queue<int>q; q.push(source); while(!q.empty()){ int u=q.front(); q.pop(); int k=Head[u]; while(k!=-1){ if(!D_vis[e[k].v]&&e[k].w){ D_vis[e[k].v]=D_vis[u]+1; q.push(e[k].v); } k=e[k].Next; } } return D_vis[meeting]; } int dfs(int u,int f) { if(u==meeting){return f;} int &k=D_num[u]; while(k!=-1){ if(D_vis[e[k].v]==D_vis[u]+1&&e[k].w){ int d=dfs(e[k].v,min(f,e[k].w)); if(d>0){ e[k].w-=d; e[k^1].w+=d; return d; } } k=e[k].Next; } return 0; } int Dinic() { int ans=0; while(bfs()){ int f; while((f=dfs(source,inf))>0){ ans+=f; } } return ans; } int city1(int x){ return x; } int city2(int x){ return x+n; } int main() { // ios::sync_with_stdio(false); // freopen("in.txt", "r", stdin); while (scanf("%d%d",&n,&m)!=EOF){ memset(Head,-1,sizeof(Head)); cnt=0; scanf("%d%d",&source,&meeting); meeting+=n; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); add_edge(city1(i),city2(i),x); add_edge(city2(i),city1(i),0); }for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add_edge(city2(x),city1(y),inf); add_edge(city1(y),city2(x),0); add_edge(city2(y),city1(x),inf); add_edge(city1(x),city2(y),0); } printf("%d\n",Dinic()); } return 0; }
原文：https://www.cnblogs.com/ZGQblogs/p/11215762.html
