网络流经典模型——最大权闭合子图
什么是闭合子图
闭合子图的概念 : 通俗点说就是选出一个图的子图，使得子图中的所有点出度指向的点依旧在这个子图内，则说明此子图是闭合子图。如下图
最大权闭合子图 : 假设每个点具有点权值，在一个图的所有闭合子图中，点权之和最大的即是最大权闭合子图
最大权闭合子图与最小割的关系
这里我们要证明最大权闭合子图的权值之和与最小割的关系
结论：最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图
证明:最小割为简单割。
因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证
证明网络中的简单割与原图中闭合图存在一一对应的关系
证明闭合图是简单割：如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。
证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。
证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图
证明比较简单，记录结论就好了
如果对最大权闭合子图建模
首先，我们有结论，最大权闭合子图权值 = 所有权值为正的权值之和 - 最大流
所以，
（1）如果当前点权值为正，建边s到u，容量为权值w；
（2）如果当前点权值为负，建边u到t，容量为权值的绝对值|w|
（3）在原图中存在的边，建边u到v，容量为INF，表示如果需要切断v就必须切断u，否则有一条容量为INF的边就不是最小割了。（就是通过这样的限制方式实现）
最后，上图的模型转化为
例题：（1）师范大学の矿山
给你n个石头，每个石头有一个价值val，有一个花费cost，在挖当前石头时，如果有石头挡在当前石头前面，只有当你挖掉前面的石头后，才能挖现在的石头，问你最小花费。
思路：最大权闭合子图裸题，对于每个石头，如果val-cost>0，建边s到i,如果val-cost<0，建边i到t，在原图中的图，建立反向图就好了，容量为INF。
（水题不要代码）
（2）BZOJ1497最大获利
对于两个点u,v，建立两个点的花费为costa+costb，但是可以获得c的利润，问你最后最大获利为多少
思路：
都告诉你最大权闭合子图了，那就往这方面想，将边权值化为点权值，比如边（u，v，w）,将他抽象为一个点x，这个点可以获利，于是他应该与源点s相连；点u，v都只能亏损（建立点的花费），向汇点建边；最后x与u，v都要建边，容量为INF，表示如果选择c，那么u和v都要选择。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn=60000+15;
const int INF=0x3f3f3f3f;
struct Edge{
int from,to,cap,flow;
Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
};
struct Dinic{
int n,m,s,t;
vector<int>G[maxn];
vector<Edge>edges;
int d[maxn];
int vis[maxn];
int cur[maxn];
void init(int n){
this->n=n;
for(int i=0;i<=n;i++)G[i].clear();
edges.clear();
}
void add_edges(int u,int v,int cap){
edges.push_back(Edge(u,v,cap,0));
edges.push_back(Edge(v,u,0,0));
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool BFS()
{
memset(vis,0,sizeof(vis));
queue<int> Q;//用来保存节点编号的
Q.push(s);
d[s]=0;
vis[s]=true;
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] && e.cap>e.flow)
{
vis[e.to]=true;
d[e.to] = d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
//a表示从s到x目前为止所有弧的最小残量
//flow表示从x到t的最小残量
int DFS(int x,int a)
{
if(x==t || a==0)return a;
int flow=0,f;//flow用来记录从x到t的最小残量
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;
}
}
if(!flow) d[x] = -1;///炸点优化
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;
}
};
Dinic dinic;
int n,m;
int val[maxn];
signed main(){
while(scanf("%d%d",&n,&m)!=EOF){
dinic.init(n+10);
int inx=n;
int s=0,t=n+m+10;
for(int i=1;i<=n;i++){
int w;
scanf("%d",&w);
dinic.add_edges(i,t,w);
}
int tot=0;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
int inx=n+i;
tot+=w;
dinic.add_edges(s,inx,w);
dinic.add_edges(inx,u,INF);
dinic.add_edges(inx,v,INF);
}
int ans=dinic.Maxflow(s,t);
printf("%d\n",tot-ans);
}
return 0;
}