http://poj.org/problem?id=2987
https://blog.csdn.net/u014686462/article/details/48533253
给一个闭合图，要求输出其最大权闭合图的权值和需要选的最少点数，最大权闭合图定义和网络流连边方式见博客。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
const int maxn=;
const LL minf=(LL)1e14;
int n,m,s,t;
LL val[maxn]={};
struct nod{
int y,next;LL v;
}e[maxn*];
int head[maxn],tot=;
queue<int>q;
int dep[maxn]={},vis[maxn]={},id[maxn]={},tai=;
void init(int x,int y,LL v){
e[++tot].y=y;e[tot].v=v;e[tot].next=head[x];head[x]=tot;
}
bool dfs(){
memset(dep,,sizeof(dep));
q.push(s);dep[s]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].next){
if(e[i].v&&!dep[e[i].y]){
dep[e[i].y]=dep[x]+;
q.push(e[i].y);
}
}
}
return dep[t];
}
LL dfs1(int x,LL fc){
if(x==t){
return fc;
}
LL he=,z;
for(int i=head[x];i;i=e[i].next){
if(dep[x]+==dep[e[i].y]){
z=dfs1(e[i].y,min(fc-he,e[i].v));
he+=z;e[i].v-=z;e[i^].v+=z;
if(he==fc)break;
}
}
return he;
}
void dfs2(int x){
if(x==t)return;
if(x!=s)id[++tai]=x;
vis[x]=;
for(int i=head[x];i;i=e[i].next){
if(e[i].v&&!vis[e[i].y]){
dfs2(e[i].y);
}
}
}
int main(){
int x,y; LL ans=;
scanf("%d%d",&n,&m);
s=n+;t=s+;
for(int i=;i<=n;i++){
scanf("%lld",&val[i]);
if(val[i]>=){init(s,i,val[i]);init(i,s,);ans=ans+val[i];}
else {init(i,t,-val[i]);init(t,i,);}
}
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
init(x,y,minf);init(y,x,);
}
while(dfs())ans-=dfs1(s,minf);
dfs2(s);
printf("%d ",tai);
printf("%lld\n",ans);
return ;
}