http://www.lydsy.com/JudgeOnline/problem.php?id=1497
思路：（最大权闭合图的思路相同）
将所有的用户群获利（正值）作为一个点连一条权值为获利值的边到st点，将所有的建站消耗（输入的是正值但是是在获利中减去的所以实质还是负值）作为一个点连一条权值为消耗值的边到ed点，再将每个用户群点和其依赖的建站点连一条权值为无穷的边，求st到ed的最大流。
此时，所求的最大获利=所有用户群获利的和-最大流。
某条st到ed的路如果得不偿失，贡献的值就是用户群获利的值；否则，贡献值为建站消耗，从而起到了选择的作用。
算是网络流的复习，用奇怪的优化过的dinic才不会超时，其他的方法算最大流都是80分。
dinic的写法和我以前看到的不一样，减少了return次数从而减少了dfs的次数，让每次dfs的值就是目前图中所有路（不重合）能得到的值，大大节省了时间。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<vector> 8 using namespace std; 9 const int maxn=55010; 10 const int minf=1<<30; 11 int n,m; 12 int a[maxn]={}; 13 int vis[maxn]={}; 14 struct nod{ 15 int y,next,v,rev; 16 }e[maxn*10]; 17 int head[maxn],dep[maxn],tot=0; 18 void init(int x,int y,int v){ 19 e[++tot].y=y;e[tot].v=v;e[tot].next=head[x],e[tot].rev=tot+1; 20 head[x]=tot; 21 e[++tot].y=x;e[tot].v=0;e[tot].next=head[y],e[tot].rev=tot-1; 22 head[y]=tot; 23 } 24 int bfs(int st,int ed){ 25 queue<int>q; 26 memset(dep,-1,sizeof(dep)); 27 dep[st]=0;q.push(st); 28 int x,y,v; 29 while(!q.empty()){ 30 x=q.front();q.pop(); 31 for(int i=head[x];i;i=e[i].next){ 32 y=e[i].y;v=e[i].v; 33 if(dep[y]==-1&&v){ 34 dep[y]=dep[x]+1;q.push(y); 35 } 36 } 37 } 38 return dep[ed]!=-1; 39 } 40 int dfs(int x,int ed,int mi){ 41 if(x==ed)return mi; 42 int y,v,f,tsn=0; 43 for(int i=head[x];i;i=e[i].next){ 44 y=e[i].y;v=e[i].v; 45 if(v&&dep[y]==dep[x]+1){ 46 f=dfs(y,ed,min(mi-tsn,v)); 47 e[i].v-=f; 48 e[e[i].rev].v+=f; 49 tsn+=f; 50 if(tsn==mi)return tsn; 51 } 52 } 53 if(!tsn)dep[x]=-1; 54 return tsn; 55 56 } 57 int dinic(int st,int ed){ 58 int ans=0; 59 while(bfs(st,ed)){ 60 ans+=dfs(st,ed,minf); 61 } 62 return ans; 63 } 64 int main(){ 65 scanf("%d%d",&n,&m); 66 int x,y,v,st=n+m+1,ed; 67 ed=st+1; 68 int ans=0; 69 for(int i=1;i<=n;i++){ 70 scanf("%d",&a[i]); 71 init(i,ed,a[i]); 72 } 73 for(int i=1;i<=m;i++){ 74 scanf("%d%d%d",&x,&y,&v); 75 ans+=v; 76 init(i+n,x,minf); 77 init(i+n,y,minf); 78 init(st,i+n,v); 79 } 80 printf("%d ",ans-dinic(st,ed)); 81 return 0; 82 }