【题解】太空飞行计划网络流24题最小割最大闭合权子图

（待更新）

Prelude

传送到LOJ
虽然是网络流24题中的T2，但是挺难的，至少我之前不知道什么是最大闭合权子图。

Solution

首先要明白什么是最大闭合权子图，然后求最小割就可以了。。。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 110;
const int MAXM = 6000;
const int INF = 0x3f3f3f3f;
namespace Dinic {
	struct Edge {
		int u,v,c,f;
		Edge() {}
		Edge(int u,int v,int c,int f):
			u(u), v(v), c(c), f(f) {}
	};
	int n,m,s,t;
	Edge edge[MAXM];
	int head[MAXN],nxt[MAXM];
	int dis[MAXN],cur[MAXN];
	void init(int _n) {
		n = _n, m = 0;
		for(int i = 0; i < n; ++i)
			head[i] = -1;
	}
	void adde(int u,int v,int c) {
		nxt[m] = head[u];
		edge[m] = Edge(u,v,c,0);
		head[u] = m++;
		nxt[m] = head[v];
		edge[m] = Edge(v,u,0,0);
		head[v] = m++;
	}
	queue<int> q;
	bool bfs() {
		for(int i = 0; i < n; ++i)
			dis[i] = INF;
		dis[s] = 0;
		q.push(s);
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = head[u]; ~i; i = nxt[i]) {
				Edge &e = edge[i];
				if(dis[e.v] == INF && e.c > e.f) {
					dis[e.v] = dis[u] + 1;
					q.push(e.v);
				}
			}
		}
		return dis[t] != INF;
	}
	int dfs(int u, int res) {
		int flow = 0, f;
		if(u == t || !res) return res;
		for(int &i = cur[u]; ~i; i = nxt[i]) {
			Edge &e = edge[i];
			if(e.c > e.f && dis[e.v] == dis[u] + 1) {
				f = dfs(e.v,min(res,e.c - e.f));
				e.f += f;
				edge[i^1].f -= f;
				flow += f;
				res -= f;
				if(!res) break;
			}
		}
		return flow;
	}
	int maxflow(int _s, int _t) {
		s = _s, t = _t;
		int flow = 0;
		while(bfs()) {
			for(int i = 0; i < n; ++i)
				cur[i] = head[i];
			flow += dfs(s,INF);
		}
		return flow;
	}
}
int get[60],yi[60][60],cost[60];
bool shi[60],yiqi[60];
int main() {
	int m,n;
	scanf("%d%d",&m,&n);
	int s = 0, t = m + n + 1;
	Dinic::init(t + 1);
	for(int i = 1; i <= m; ++i) {
		yi[i][0] = 0;
		scanf("%d",get + i);
		Dinic::adde(s,i,get[i]);
		while(1) {
			char getc = getchar();
			if(getc == '\n' || getc == '\r') break;
			scanf("%d",&yi[i][++yi[i][0]]);
			Dinic::adde(i,m+yi[i][yi[i][0]],INF);
		}
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d",cost+i);
		Dinic::adde(m+i,t,cost[i]);
	}
	int _ans = Dinic::maxflow(s,t);
	int ans = 0;
	for(int i = 1; i <= m; ++i)
		ans += get[i];
	ans -= _ans;
	memset(shi,0,sizeof shi);
	for(int i = 0; i < Dinic::m; ++i) {
		if(Dinic::edge[i].u != s) continue;
		if(Dinic::dis[Dinic::edge[i].v] != INF) shi[Dinic::edge[i].v] = 1;
	}
	memset(yiqi,0,sizeof yiqi);
	for(int i = 1; i <= m; ++i) {
		if(!shi[i]) continue;
		printf("%d ",i);
		for(int j = 1; j <= yi[i][0]; ++j)
			yiqi[yi[i][j]] = 1;
	}
	puts("");
	for(int i = 1; i <= n; ++i)
		if(yiqi[i]) printf("%d ",i);
	puts("");
	printf("%d\n",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN = 110;

const int MAXM = 6000;

const int INF = 0x3f3f3f3f;

namespace Dinic {

struct Edge {

int u,v,c,f;

Edge() {}

Edge(int u,int v,int c,int f):

u(u), v(v), c(c), f(f) {}

};

int n,m,s,t;

Edge edge[MAXM];

int head[MAXN],nxt[MAXM];

int dis[MAXN],cur[MAXN];

void init(int _n) {

n = _n, m = 0;

for(int i = 0; i < n; ++i)

head[i] = -1;

}

void adde(int u,int v,int c) {

nxt[m] = head[u];

edge[m] = Edge(u,v,c,0);

head[u] = m++;

nxt[m] = head[v];

edge[m] = Edge(v,u,0,0);

head[v] = m++;

}

queue<int> q;

bool bfs() {

for(int i = 0; i < n; ++i)

dis[i] = INF;

dis[s] = 0;

q.push(s);

while(!q.empty()) {

int u = q.front();

q.pop();

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

Edge &e = edge[i];

if(dis[e.v] == INF && e.c > e.f) {

dis[e.v] = dis[u] + 1;

q.push(e.v);

}

return dis[t] != INF;

}

int dfs(int u, int res) {

int flow = 0, f;

if(u == t || !res) return res;

for(int &i = cur[u]; ~i; i = nxt[i]) {

Edge &e = edge[i];

if(e.c > e.f && dis[e.v] == dis[u] + 1) {

f = dfs(e.v,min(res,e.c - e.f));

e.f += f;

edge[i^1].f -= f;

flow += f;

res -= f;

if(!res) break;

}

return flow;

}

int maxflow(int _s, int _t) {

s = _s, t = _t;

int flow = 0;

while(bfs()) {

for(int i = 0; i < n; ++i)

cur[i] = head[i];

flow += dfs(s,INF);

}

return flow;

}

int get[60],yi[60][60],cost[60];

bool shi[60],yiqi[60];

int main() {

int m,n;

scanf("%d%d",&m,&n);

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

Dinic::init(t + 1);

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

yi[i][0] = 0;

scanf("%d",get + i);

Dinic::adde(s,i,get[i]);

while(1) {

char getc = getchar();

if(getc == '\n' || getc == '\r') break;

scanf("%d",&yi[i][++yi[i][0]]);

Dinic::adde(i,m+yi[i][yi[i][0]],INF);

}

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

scanf("%d",cost+i);

Dinic::adde(m+i,t,cost[i]);

}

int _ans = Dinic::maxflow(s,t);

int ans = 0;

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

ans += get[i];

ans -= _ans;

memset(shi,0,sizeof shi);

for(int i = 0; i < Dinic::m; ++i) {

if(Dinic::edge[i].u != s) continue;

if(Dinic::dis[Dinic::edge[i].v] != INF) shi[Dinic::edge[i].v] = 1;

}

memset(yiqi,0,sizeof yiqi);

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

if(!shi[i]) continue;

printf("%d ",i);

for(int j = 1; j <= yi[i][0]; ++j)

yiqi[yi[i][j]] = 1;

}

puts("");

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

if(yiqi[i]) printf("%d ",i);

puts("");

printf("%d\n",ans);

return 0;

}