http://www.lydsy.com/JudgeOnline/problem.php?id=1497
思路：（最大权闭合图的思路相同）
将所有的用户群获利（正值）作为一个点连一条权值为获利值的边到st点，将所有的建站消耗（输入的是正值但是是在获利中减去的所以实质还是负值）作为一个点连一条权值为消耗值的边到ed点，再将每个用户群点和其依赖的建站点连一条权值为无穷的边，求st到ed的最大流。
此时，所求的最大获利=所有用户群获利的和-最大流。
某条st到ed的路如果得不偿失，贡献的值就是用户群获利的值；否则，贡献值为建站消耗，从而起到了选择的作用。
算是网络流的复习，用奇怪的优化过的dinic才不会超时，其他的方法算最大流都是80分。
dinic的写法和我以前看到的不一样，减少了return次数从而减少了dfs的次数，让每次dfs的值就是目前图中所有路（不重合）能得到的值，大大节省了时间。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int maxn=;
const int minf=<<;
int n,m;
int a[maxn]={};
int vis[maxn]={};
struct nod{
int y,next,v,rev;
}e[maxn*];
int head[maxn],dep[maxn],tot=;
void init(int x,int y,int v){
e[++tot].y=y;e[tot].v=v;e[tot].next=head[x],e[tot].rev=tot+;
head[x]=tot;
e[++tot].y=x;e[tot].v=;e[tot].next=head[y],e[tot].rev=tot-;
head[y]=tot;
}
int bfs(int st,int ed){
queue<int>q;
memset(dep,-,sizeof(dep));
dep[st]=;q.push(st);
int x,y,v;
while(!q.empty()){
x=q.front();q.pop();
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(dep[y]==-&&v){
dep[y]=dep[x]+;q.push(y);
}
}
}
return dep[ed]!=-;
}
int dfs(int x,int ed,int mi){
if(x==ed)return mi;
int y,v,f,tsn=;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(v&&dep[y]==dep[x]+){
f=dfs(y,ed,min(mi-tsn,v));
e[i].v-=f;
e[e[i].rev].v+=f;
tsn+=f;
if(tsn==mi)return tsn;
}
}
if(!tsn)dep[x]=-;
return tsn; }
int dinic(int st,int ed){
int ans=;
while(bfs(st,ed)){
ans+=dfs(st,ed,minf);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
int x,y,v,st=n+m+,ed;
ed=st+;
int ans=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
init(i,ed,a[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&v);
ans+=v;
init(i+n,x,minf);
init(i+n,y,minf);
init(st,i+n,v);
}
printf("%d\n",ans-dinic(st,ed));
return ;
}