题意: 有n个基站可以建立，然后m个团体会使用这些基站进行工作，地i个团体会适应Ai Bi 这两个基站， 如果建成收益Ci, 第j个基站花费Pj，求如何建立使得收益最大，
将每个团体看以一个点，然后从这个点出发向那两个点建一条边，他自己想s建立一个为Ci的边，第j个基站想t建立一个容量为Pj的边，跑一遍最小割，然后所有正权减去这个最小割得到答案
#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn=57000; const int INF=2147483647; struct Dinic { struct Edge{ int from,to,cap,flow; Edge(int cfrom=0,int cto=0,int ccap=0,int cflow=0) { from=cfrom; to=cto; cap=ccap; flow=cflow; } }; int n,m,s,t; vector<Edge>edges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { m=0; for(int i=0; i<=n; i++)G[i].clear(); edges.clear(); } void addEdge(int from,int to, int cap) { edges.push_back(Edge(from,to,cap,0) ); edges.push_back(Edge(to,from,0,0)); m+=2; G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0; i<G[x].size(); i++) { Edge &e = edges[G[x][i]]; if(vis[e.to]==false&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t||a==0)return a; int flow=0,f; for(int &i=cur[x]; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } int Maxflow(int s,int t) { this->s=s;this->t=t; int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(s,INF); } return flow; } }T; int P[maxn]; int A[maxn],B[maxn],X[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { int S=0; T.init(n+m+2); int ss=n+m+1,tt=n+m+2; for(int i=1; i<=n; i++) { scanf("%d",&P[i]); S+=P[i]; T.addEdge(i,tt,P[i]); } int S1=0; for(int i=1; i<=m; i++) { scanf("%d%d%d",&A[i],&B[i],&X[i]); T.addEdge(ss,n+i,X[i]); S+=X[i]; S1+=X[i]; } for(int j=1; j<=m; j++) { T.addEdge(n+j,A[j],S); T.addEdge(n+j,B[j],S); } int ans=T.Maxflow(ss,tt); printf("%d\n",S1-ans); } return 0; }
ISAP
#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn=57000; const int INF=2147483647; struct ISAP { struct Edge{ int from,to,cap,flow; Edge(int cfrom=0,int cto=0,int ccap=0,int cflow=0) { from=cfrom; to=cto; cap=ccap; flow=cflow; } }; int n,m,s,t; vector<Edge>edges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int p[maxn]; int num[maxn]; void init(int n) { m=0; this->n=n; for(int i=0; i<=n; i++)G[i].clear(); edges.clear(); } void addEdge(int from,int to, int cap) { edges.push_back(Edge(from,to,cap,0) ); edges.push_back(Edge(to,from,0,0)); m+=2; G[from].push_back(m-2); G[to].push_back(m-1); } void BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(t); d[t]=0; vis[t]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0; i<G[x].size(); i++) { Edge &e = edges[G[x][i]]; if(vis[e.to]==false) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } } int Augment() { int x=t,a=INF; while(x!=s) { Edge &e=edges[p[x]]; a=min(a,e.cap-e.flow); x=edges[p[x]].from; } x=t; while(x!=s) { edges[p[x]].flow+=a; edges[p[x]^1].flow-=a; x=edges[p[x]].from; } return a; } int Maxflow(int s,int t) { this->s=s;this->t=t; int flow=0; BFS(); memset(num,0,sizeof(num)); for(int i=0; i<=n; i++)num[d[i]]++; int x=s; memset(cur,0,sizeof(cur)); while(d[s]<n) { if(x==t) { flow+=Augment(); x=s; } int ok=0; for(int i=cur[x]; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(e.cap>e.flow&&d[x]==d[e.to]+1) { ok=1; p[e.to]=G[x][i]; cur[x]=i; x=e.to; break; } } if(ok==0) { int m=n-1; for(int i=0; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(e.cap>e.flow)m=min(m,d[e.to]); } if(--num[d[x]]==0)break; num[d[x]=m+1]++; cur[x]=0; if(x!=s)x=edges[p[x]].from; } } return flow; } }T; int P[maxn]; int A[maxn],B[maxn],X[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { int S=0; T.init(n+m+2); int ss=n+m+1,tt=n+m+2; for(int i=1; i<=n; i++) { scanf("%d",&P[i]); S+=P[i]; T.addEdge(i,tt,P[i]); } int S1=0; for(int i=1; i<=m; i++) { scanf("%d%d%d",&A[i],&B[i],&X[i]); T.addEdge(ss,n+i,X[i]); S+=X[i]; S1+=X[i]; } for(int j=1; j<=m; j++) { T.addEdge(n+j,A[j],S); T.addEdge(n+j,B[j],S); } int ans=T.Maxflow(ss,tt); printf("%d\n",S1-ans); } return 0; }
原文：http://www.cnblogs.com/Opaser/p/4918376.html
