最大权闭合子图

胡伯涛论文真是个好东西.jpg

求一个有向图的最大权闭合子图,常应用于有先决条件的最优化问题中

将所有正权点与源点相连,容量为点权;

将所有负权点与汇点相连,容量为点权的相反数;

将原图中的边相连,容量为INF

可以发现,所有正点权之和-最小割即为答案

证明见胡伯涛论文

如何输出该子图

可以发现求出最小割后的残量网络中与s点相连的点即为所求

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <queue>

using namespace std;

const int MAXN=305,MAXM=20005;

int n,s,t,m,head[MAXN],cur[MAXN],dep[MAXN],maxflow,nume;

struct edge{

	int to,nxt,flow,cap;

}e[MAXM];

void adde(int from,int to,int cap){

	e[++nume].to=to;

	e[nume].nxt=head[from];

	head[from]=nume;

	e[nume].cap=cap;

}

queue<int >q;

bool bfs(){

	memset(dep,0,sizeof(dep));

	q.push(s);dep[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(!dep[v]&&e[i].flow<e[i].cap){

				dep[v]=dep[u]+1;

				q.push(v);

			}

		}

	}

	return dep[t];

}

int dfs(int u,int flow){

	if(u==t) return flow;

	int tot=0;

	for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){

		int v=e[i].to;

		if(dep[v]==dep[u]+1&&e[i].flow<e[i].cap){

			if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){

				e[i].flow+=t;

				e[((i-1)^1)+1].flow-=t;

				tot+=t;

			}

		}

	}

	return tot;

}

void dinic(){

	while(bfs()){

		for(int i=s;i<=t;i++) cur[i]=head[i];

		maxflow+=dfs(s,0x3f3f3f3f);

	}

}

int main(){

	cin>>m>>n;

	int tot=0;

	s=0;t=m+n+1;

	for(int i=1;i<=m;i++){

		int t;

		cin>>t;

		tot+=t;

		adde(s,i,t);adde(i,s,0);

		while(cin.peek()!='\r'&&cin.peek()!='\n'&&cin.peek()!=EOF){

			scanf("%d",&t);

			adde(i,t+m,0x3f3f3f3f);

			adde(t+m,i,0);

		}

	}

	for(int i=1;i<=n;i++){

		int wei;

		cin>>wei;

		adde(i+m,t,wei);adde(t,i+m,0);

	}

	dinic();

	for(int i=1;i<=m;i++) if(dep[i]) printf("%d ",i);

	printf("\n");

	for(int i=m+1;i<=m+n;i++) if(dep[i]) printf("%d ",i-m);

	printf("\n");

	cout<<tot-maxflow<<endl;

}