P2754 [CTSC1999]家園

\(\color{#0066ff}{題目描述}\)

由于人類對自然資源的消耗，人們意識到大約在 2300 年之後，地球就不能再居住了。于是在月球上建立了新的綠地，以便在需要時移民。令人意想不到的是，2177 年冬由于未知的原因，地球環境發生了連鎖崩潰，人類必須在最短的時間内遷往月球。

現有 n 個太空站位于地球與月球之間，且有 m 艘公共交通太空梭在其間來回穿梭。每個太空站可容納無限多的人，而每艘太空梭 i 隻可容納 H[i]個人。每艘太空梭将周期性地停靠一系列的太空站，例如：(1，3，4)表示該太空梭将周期性地停靠太空站 134134134…。每一艘太空梭從一個太空站駛往任一太空站耗時均為 1。人們隻能在太空梭停靠太空站(或月球、地球)時上、下船。

初始時所有人全在地球上，太空梭全在初始站。試設計一個算法，找出讓所有人盡快地全部轉移到月球上的運輸方案。

對于給定的太空梭的資訊，找到讓所有人盡快地全部轉移到月球上的運輸方案。

\(\color{#0066ff}{輸入格式}\)

第 1 行有 3 個正整數 n（太空站個數），m（太空梭個數）和 k（需要運送的地球上的人的個數）。其中 n<=13 m<=20, 1<=k<=50。

接下來的 m 行給出太空梭的資訊。第 i+1 行說明太空梭 pi。第 1 個數表示 pi 可容納的人數 Hpi；第 2 個數表示 pi 一個周期停靠的太空站個數 r，1<=r<=n+2；随後 r 個數是停靠的太空站的編号(Si1,Si2,…,Sir)，地球用 0 表示，月球用-1 表示。

時刻 0 時，所有太空梭都在初始站，然後開始運作。在時刻 1，2，3…等正點時刻各艘太空梭停靠相應的太空站。人隻有在 0,1,2…等正點時刻才能上下太空梭。

\(\color{#0066ff}{輸出格式}\)

\(\color{#0066ff}{輸入樣例}\)

2 2 1
1 3 0 1 2
1 3 1 2 -1
           

\(\color{#0066ff}{輸出樣例}\)

5
           

\(\color{#0066ff}{資料範圍與提示}\)

\(\color{#0066ff}{題解}\)

注意，比如有兩輛車，在某一時刻，一個從1到2，一個從2到3，那麼人可不能在2時間内到3

也就是說，每次在網絡流隻能流1

可以利用分層的思想

枚舉時間，每個時間建立一層空間站的圖

起點隻連地球，每層的月球都向終點連

直到dinic的最大流比k大就輸出就行了

注意判無解

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define _ 0
#define LL long long
inline LL in() {
	LL x = 0, f = 1; char ch;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return x * f;
}
struct node {
	int to, dis;
	node *nxt, *rev;
	node(int to = 0, int dis = 0, node *nxt = NULL):to(to), dis(dis), nxt(nxt) {}
	void *operator new (size_t) {
		static node *S = NULL, *T = NULL;
		return ((S == T) && (T = (S = new node[1024]) + 1024)),S++; 
	}
};
const int inf = 0x7fffffff;
int n, m, s, t, k, ans;
const int maxn = 1000500;
typedef node* nod;
nod head[maxn], cur[maxn];
int dep[maxn], init[maxn], to[55][55], zz[55];
std::queue<int> q;
inline void add(int from, int to, int dis) {
	nod o = new node(to, dis, head[from]);
	head[from] = o;
}
inline void link(int from, int to, int dis) {
	add(from, to, dis);
	add(to, from, 0);
	head[from]->rev = head[to];
	head[to]->rev = head[from];
}
inline bool bfs() {
	for(int i = s; i <= t; i++) cur[i] = head[i], dep[i] = 0;
	dep[s] = 1;
	q.push(s);
	while(!q.empty()) {
		int tp = q.front();
		q.pop();
		for(nod i = head[tp]; i; i = i->nxt) {
			if(!dep[i->to] && i->dis > 0) {
				dep[i->to] = dep[tp] + 1;
				q.push(i->to);
			}
		}
	}
	return dep[t];
}
inline int dfs(int x, int change) {
	if(x == t || !change) return change;
	int flow = 0, ls;
	for(nod i = cur[x]; i; i = i->nxt) {
		cur[x] = i;
		if(dep[i->to] == dep[x] + 1 && (ls = dfs(i->to, std::min(change, i->dis)))) {
			change -= ls;
			flow += ls;
			i->dis -= ls;
			i->rev->dis += ls;
			if(!change) break;
		}
	}
	return flow;
}
int main() {
	n = in(), m = in(), k = in();
	int num = 0, len = n + 2;
	s = 0, t = 905050;
	for(int i = 1; i <= m; i++) {
		init[i] = in();
		zz[i] = 1;
		to[i][0] = in();
		for(int j = 1; j <= to[i][0]; j++) {
			to[i][j] = in();
			if(to[i][j] == 0) to[i][j] = n + 1;
			if(to[i][j] == -1) to[i][j] = n + 2;
		}
	}
	link(s, n+1, inf);
	while(1) {	
		ans++;
		if(ans != 1)
			for(int i = 1; i <= len; i++)
				link(i + len * (ans - 2), i + len * (ans - 1), inf); 
		for(int i = 1; i <= m; i++) {
			int now = to[i][zz[i]];
			zz[i]++, zz[i] %= to[i][0];
			if(!zz[i]) zz[i] = to[i][0];
			int go = to[i][zz[i]];
			link(now + len * (ans - 1), go + len * ans, init[i]);
		}
		link(len + len * ans, t, inf);
		while(bfs()) num += dfs(s, inf);
		if(num >= k) break;
		if(ans == 498) break;
	}
	printf("%d", ans == 498? 0 : ans);
	return 0 ;
}
           

----olinr