BZOJ 2502 清理雪道（有源汇上下界最小流）

题面

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

题解

新建一个源点表示直升机（…），那么从直升机流出的流量必须覆盖所有的边。那么边的下界是1，上界inf，然后套用有源汇上下界最小流就行了。这里我没有建汇点，所以最后需要每个点都向s连边。

CODE

#include <bits/stdc++.h>

using namespace std;

template<class T>inline void read(T &x) {

	char ch; while(!isdigit(ch=getchar()));

	for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');

}

const int MAXN = 105;

const int MAXM = 10005+205;

const int inf = 0x3f3f3f3f;

int n, m, out[MAXN], in[MAXN];

int info[MAXN], fir[MAXN], to[MAXM<<1], nxt[MAXM<<1], c[MAXM<<1], cnt = 1;

inline void link(int u, int v, int cc) {

	to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; c[cnt] = cc;

	to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt; c[cnt] = 0;

}

int S, T, dis[MAXN], ans;

queue<int>q;

bool vis[MAXN], inq[MAXN];

bool bfs() {

	memset(dis, -1, sizeof dis);

	dis[S] = 0; q.push(S);

	while(!q.empty()) {

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

		for(int i = fir[u]; i; i = nxt[i])

			if(c[i] && !~dis[to[i]])

				dis[to[i]] = dis[u] + 1, q.push(to[i]);

	}

	return ~dis[T];

}

int aug(int u, int Max) {

	if(u == T) return Max;

	vis[u] = 1; int flow = 0, delta;

	for(int v, &i = info[u]; i; i = nxt[i])

		if(c[i] && !vis[v=to[i]] && dis[v] == dis[u] + 1 && (delta=aug(v, min(Max-flow, c[i])))) {

			c[i] -= delta, c[i^1] += delta, flow += delta;

			if(flow == Max) break;

		}

	vis[u] = 0; return flow;

}

int Maxflow(int s, int t) {

	int re = 0; S = s, T = t;

	while(bfs()) memcpy(info, fir, sizeof info), re += aug(S, inf);

	return re;

}

int main () {

	read(n);

	int Ans = 0; int s = n+1;

	for(int i = 1, j, k, w; i <= n; ++i) {

		link(s, i, inf);

		read(k); out[i] = k;

		while(k--) {

			read(j);

			link(i, j, inf);

			++in[j];

		}

	}

	int ss = n+2, tt = n+3;

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

		if(in[i] > out[i]) link(ss, i, in[i]-out[i]);

		if(in[i] < out[i]) link(i, tt, out[i]-in[i]);

	}

	Maxflow(ss, tt);

	for(int i = 1; i <= n; ++i) link(i, s, inf);

	printf("%d\n", Maxflow(ss, tt));

}