搭配飞行员

求二分图最大匹配。

分析

网络流建模要找到问题的关键特点，用连边，流量（以及费用）把原问题转化成网络流问题，包括最大流，最小割，费用流。

二分图最大匹配的特点是每个点最多属于一条匹配边。这相当于是说，每个点只能流过一次。要求的是最大匹配，可以得出建模为：

对于左边的点(x)，连边((S,x,1))
对于右边的点(y)，连边((y,T,1))
对于原图中的边((x,y))，连边((x,y,1))

最大流即为二分图的最大匹配。

注意到这个解法中，我们实际上是把一个匹配转化成了1的流量，求出的最大流满足每个点都只流过了一次，故符合匹配的定义。又因为是最大流，所以得到的是最大匹配。

代码

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=101;
const int inf=1e9+7;
const int maxm=1e4+1;
int que[maxn],d[maxn],ql,qr;
struct edge {
	int v,w,nxt;
};
struct graph {
	edge e[maxm<<3];
	int h[maxn],tot;
	graph ():tot(1) {}
	void add(int u,int v,int w) {
		e[++tot]=(edge){v,w,h[u]};
		h[u]=tot;
	}
	bool bfs(int s,int t) {
		que[ql=qr=1]=s;
		memset(d,0,sizeof d);
		d[s]=1;
		while (ql<=qr) {
			int x=que[ql++];
			for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!d[v] && e[i].w) {
				d[v]=d[x]+1;
				if (v==t) return true;
				que[++qr]=v;
			}
		}
		return false;
	}
	int dfs(int x,int t,int mx) {
		if (x==t) return mx;
		int flow=0;
		for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (d[v]==d[x]+1 && e[i].w) {
			int mi=min(e[i].w,mx);
			int tmp=dfs(v,t,mi);
			if (!tmp) {
				d[v]=0;
				continue;
			}
			e[i].w-=tmp;
			e[i^1].w+=tmp;
			flow+=tmp;
			mx-=tmp;
			if (!mx) break;
		}
		return flow;
	}
	int maxflow(int S,int T) {
		int ret=0;
		while (bfs(S,T)) {
			ret+=dfs(S,T,inf);
		}
		return ret;
	}
} A;
int main() {
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	int n,m,x,y;
	scanf("%d%d",&n,&m);
	int S=0,T=n+1;
	for (int i=1;i<=m;++i) A.add(S,i,1),A.add(i,S,0);
	for (int i=m+1;i<=n;++i) A.add(i,T,1),A.add(T,i,0);
	while (~scanf("%d%d",&x,&y)) A.add(x,y,1),A.add(y,x,0);
	int ans=A.maxflow(S,T);
	printf("%d
",ans);
}

太空飞行计划

求最大权闭合子图，并输出方案。

分析

对于有向图(G)的闭合图(S)是指一个(G)的一个子图满足不存在((u,v),uin S,v otin S)。

最大权闭合子图问题是指，每个点有点权，有正有负，求一个闭合子图使得其中的点权值最大。

对于选择问题，可以考虑能否使用割的方法，因为一个割把整个图分成了两部分，即选和不选。

现有的网络流模型可以解决最小割问题（最大流最小割定理），所以可以想办法把这个问题变成最小割问题。由于要使点权最大，那么我们可以把一个东西减去最小割，得到答案。

我们把负权点的权值取绝对值。我们要的最大权闭合图的权值(W=选择的正权点权值和-选择的负权点权值和)。

设(sum=所有正权点权值和)，令(C=sum-W=不选择的正权点权值和+选择的负权点权值和)，这样我们不仅就化解了负权问题，而且得到了一个漂亮的表达：不选的正的权值和+选择的负的权值绝对值和。如果由于(W)要最大，(sum)是一定的，而且有(W=sum-C)，所以我们只要令(C)最小即可。

建图如下：

对于正权点(x)，连边((S,x,a[x]))
对于负权点(y)，连边((y,T,-a[y]))
对于原图上的点，连边((x,y,infty))

在这个图上求最小割，一定不会割掉中间的边。这是因为，割掉所有((S,x))和((y,T))必定是一个合法的割。所以最小割一定小于这个值，所以不可能含有无限大。

所以这个割是一个简单割（所有割边都直接连接(S)或(T)）。这个简单割把图分成了两部分，(S)集和(T)集。我们看看(S)集包含的点是什么。

(S)集中的点，必定是没有割开((S,x))的点和割开了((y,T))的点。也就是说，这个最小割的值就是我们的(C)。

用总正权点和减去最小割就是答案啦。

这里还要求输出方案。我们要输出的就是(S)集，也就是到最后(S)还可以到达的点，也就是dinic算法中最后的层次图。

代码

#include<cstdio>
#include<cctype>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf=1e9+7;
const int maxn=101;
const int maxm=1e4+1;
int read(int &x) {
	x=0;
	int f=1;
	char c=getchar();
	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
	for (;isdigit(c);c=getchar()) x=x*10+c-'0';
	return c!='
' && c!='
';
}
struct edge {
	int v,w,nxt;
} e[maxm<<3];
int h[maxn],tot=1;
void add(int u,int v,int w=0) {
	e[++tot]=(edge){v,w,h[u]};
	h[u]=tot;
} 
int que[maxn],ql,qr,d[maxn];
bool bfs(int s,int t) {
	memset(d,0,sizeof d);
	d[s]=1;
	que[ql=qr=1]=s;
	while (ql<=qr) {
		int x=que[ql++];
		for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (!d[v] && e[i].w) {
			d[v]=d[x]+1;
			if (v==t) return true;
			que[++qr]=v;
		}
	}
	return false;
}
int dfs(int x,int t,int mx) {
	if (x==t) return mx;
	int flow=0;
	for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (d[v]==d[x]+1 && e[i].w) {
		int mi=min(mx,e[i].w);
		int tmp=dfs(v,t,mi);
		if (!tmp) {
			d[v]=0;
			continue;
		}
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		flow+=tmp;
		mx-=tmp;
		if (!mx) break;
	}
	return flow;
}
int maxflow(int s,int t) {
	int ret=0;
	while (bfs(s,t)) ret+=dfs(s,t,inf);
	return ret;
}
int a[maxn<<1];
int main() {
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	int n,m;
	read(n),read(m);
	int S=0,T=n+m+1,sum=0;
	for (int i=1;i<=n;++i) {
		int x,r=read(a[i]);
		add(S,i,a[i]),add(i,S,0);
		sum+=a[i];
		if (!r) continue;
		do {
			r=read(x);
			add(i,x+n,inf);
			add(x+n,i,0);
		} while (r);
	}
	for (int i=n+1;i<=n+m;++i) {
		read(a[i]);
		add(i,T,a[i]),add(T,i,0);
	}
	int ans=maxflow(S,T);
	for (int i=1;i<=n;++i) if (d[i]) printf("%d ",i);
	puts("");
	for (int i=n+1;i<=n+m;++i) if (d[i]) printf("%d ",i-n);
	puts("");
	printf("%d
",sum-ans);
	return 0;
}