https://www.luogu.org/problemnew/show/P4174
最大权闭合子图的模板
每个通讯站建一个点，点权为-Pi；每个用户建一个点，点权为Ci，分别向Ai和Bi对应的点连边；然后就可以跑了
方法是：
建新源S和新汇T，从S向所有正权点连边，容量为点权值；从所有负权点向T连边，容量为点权值的相反数；原图中所有边容量设为无穷大
跑S到T最大流
原因：（网上都有，自己研究的也不知道有没有偏差）
找出图的任意一个割，其中：
显然不可能割掉容量为无穷大的边；
割掉一条S到u的边，表示不取点u，同时舍弃u点的价值；
割掉一条v到T的边，表示取点v，同时加上v点的代价；
能保证割完这个割中的边后，S到T不连通，即保证不存在任意路径，从S到u经过一些点到v再到T，即保证不存在一个u点需要被取，但是它能到达的一个节点v没有被取。
因此，一个割对应一种闭合子图方案
同样的，可以证明一种闭合子图方案一定对应这样的一个割。
那么，求出最小割，就求出了最小的"舍弃的价值和"+"加上的代价和"，设其为x，则最大权闭合子图的点权和等于所有正点权和-x，而最小割等于最大流
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace F
{ struct E
{
int to,nxt,from,cap,flow;
}e[];
int f1[],ne=;
int S,T,n;
int d[];
bool bfs()
{
int k,u;
memset(d,,sizeof(int)*(n+));
queue<int> q;
q.push(S);d[S]=;
while(!q.empty())
{
u=q.front();q.pop();
for(k=f1[u];k;k=e[k].nxt)
if(!d[e[k].to]&&e[k].cap>e[k].flow)
{
d[e[k].to]=d[u]+;
//if(e[k].to==T) return 1;
q.push(e[k].to);
}
}
//return 0;
return d[T];
}
int cur[];
int dfs(int u,int x)
{
if(u==T||x==) return x;
int flow=,f;
for(int &k=cur[u];k;k=e[k].nxt)
if(e[k].cap>e[k].flow&&d[e[k].to]==d[u]+)
{
f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
e[k].flow+=f;e[k^].flow-=f;flow+=f;
if(flow==x) return flow;
}
return flow;
}
int solve()
{
int flow=;
while(bfs())
{
memcpy(cur,f1,sizeof(int)*(n+));
flow+=dfs(S,0x3f3f3f3f);
}
return flow;
}
void me(int a,int b,int c)
{
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[ne].from=a;e[ne].cap=c;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
e[ne].from=b;e[ne].cap=;
} }
int n,m;
int main()
{
int i,a,b,c,ss=,t;
scanf("%d%d",&n,&m);F::n=n+m+;F::S=n+m+;F::T=n+m+;
for(i=;i<=n;i++)
{
scanf("%d",&t);
F::me(i,F::T,t);
//ss-=t;
}
for(i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
F::me(F::S,i+n,c);
F::me(i+n,a,0x3f3f3f3f);
F::me(i+n,b,0x3f3f3f3f);
ss+=c;
}
printf("%d",ss-F::solve());
return ;
}
upd20190307:
貌似cf出了重题，但是要改longlonghttps://codeforces.com/problemset/problem/1082/G
https://www.luogu.org/problemnew/show/P2762
这题也是一样，但是要输出方案
按照上面的方法，只要找出任意一组最小割就容易找到输出方法了
怎么找最小割？只要找出跑出最大流以后，找出残量网络中源点S能到达的点集s1，取t1=所有点的集合-s1，那么割掉原图中所有s1,t1间的边即可
这里面有一个看起来比较靠谱的证明：https://hihocoder.com/problemset/problem/1378
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace F
{ struct E
{
int to,nxt,from,cap,flow;
}e[];
int f1[],ne=;
int S,T,n;
int d[];
bool bfs()
{
int k,u;
memset(d,,sizeof(int)*(n+));
queue<int> q;
q.push(S);d[S]=;
while(!q.empty())
{
u=q.front();q.pop();
for(k=f1[u];k;k=e[k].nxt)
if(!d[e[k].to]&&e[k].cap>e[k].flow)
{
d[e[k].to]=d[u]+;
//if(e[k].to==T) return 1;
q.push(e[k].to);
}
}
//return 0;
return d[T];
}
int cur[];
int dfs(int u,int x)
{
if(u==T||x==) return x;
int flow=,f;
for(int &k=cur[u];k;k=e[k].nxt)
if(e[k].cap>e[k].flow&&d[e[k].to]==d[u]+)
{
f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
e[k].flow+=f;e[k^].flow-=f;flow+=f;
if(flow==x) return flow;
}
return flow;
}
int solve()
{
int flow=;
while(bfs())
{
memcpy(cur,f1,sizeof(int)*(n+));
flow+=dfs(S,0x3f3f3f3f);
}
return flow;
}
void me(int a,int b,int c)
{
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[ne].from=a;e[ne].cap=c;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
e[ne].from=b;e[ne].cap=;
} } int n,m;
char tools[];
bool ok[];
int tt[];
void work()
{
int k,u;
memset(ok,,sizeof(bool)*(n+));
queue<int> q;
q.push(F::S);ok[F::S]=;
using F::f1;using F::e;
while(!q.empty())
{
u=q.front();q.pop();
for(k=f1[u];k;k=e[k].nxt)
if(!ok[e[k].to]&&e[k].cap>e[k].flow)
{
q.push(e[k].to);
ok[e[k].to]=;
}
}
for(int i=;i<=F::n;i++)
if(ok[i])
{
for(k=f1[i];k;k=e[k].nxt)
if(k%==&&!ok[e[k].to])
tt[++tt[]]=k;
}
}
bool nok[];
int main()
{
int i,a,b,c,ss=,t;
scanf("%d%d",&m,&n);F::n=n+m+;F::S=n+m+;F::T=n+m+;
for(i=;i<=m;i++)
{
scanf("%d",&t);
F::me(F::S,i,t);
ss+=t;
cin.getline(tools,);
int ulen=,tool;
while(sscanf(tools+ulen,"%d",&tool)==)
{
F::me(i,tool+m,0x3f3f3f3f);
if(tool==)
ulen++;
else
{
while(tool)
{
tool/=;
ulen++;
}
}
ulen++;
}
}
for(i=;i<=n;i++)
{
scanf("%d",&t);
F::me(i+m,F::T,t);
}
int an=ss-F::solve();
work();
for(i=;i<=tt[];i++)
{
using F::e;
if(e[tt[i]].from==F::S)
{
nok[e[tt[i]].to]=;
}
}
for(i=;i<=m;i++)
if(!nok[i])
printf("%d ",i);
puts("");
for(i=;i<=tt[];i++)
{
using F::e;
if(e[tt[i]].to==F::T)
{
printf("%d ",e[tt[i]].from-m);
}
}
puts("");
printf("%d",an);
return ;
}