UVa 10779 Collectors Problem

題意：
    有N個人(含Bob)以及M種貼紙(編號1~M)，每個人手上有不同種類的貼紙數張，Bob要透過和別人交換貼紙使得他擁有最多種類的貼紙。交換規則為，除了Bob以外的其他人只與Bob交換，且只有當手中該種類貼紙大於1張時才會交換沒有的種類，也就是Bob要用某甲手中沒有的貼紙種類與某甲交換，且某甲只當該種類他有大於1張時他才願意換出那張貼紙。
    輸入第一行N M，接下來N行，每行第一個數字K表示那個人有K張貼紙，後面K個數字分別為每張貼紙的種類編號。N行中第一行為Bob。
    輸出Bob最多能擁有幾種貼紙。

想法：
    建圖做最大流，建圖方法為：

1. 每個人i擁有j種類貼紙d張，則cap[i][j]=d，表示人與該種貼紙之間的容量為那個人擁有該種貼紙的張數。
2. "除了Bob以外"，每個人i如果擁有j種類貼紙(也就是cap[i][j]>=1)，則將cap[i][j]--，因為他要保留一張絕對不交換出去，如果cap[i][j]==0，表示那個人沒有j種類貼紙，所以他願意換入該種類貼紙1張，因此把cap[j][i]=1。
3. 因為最後只要輸出Bob有幾種貼紙，建立每種貼紙到super sink(T)的容量為1。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	int cap[40][40], flow[40][40];
	int bottleneck[40], pre[40];
	int main()
	{
	int T, Case = 1, N, M, K;
	scanf("%d", &T);
	while (T--) {
	scanf("%d %d", &N, &M);
	// Initial
	int T = N+M+1; // super sink
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	// Input & Build graph
	for (int i = 1; i <= N; ++i) {
	scanf("%d", &K);
	for (int j = 1, ki; j <= K; ++j) {
	scanf("%d", &ki);
	++cap[i][N+ki];
	}
	}
	for (int i = 2; i <= N; ++i) {
	for (int j = N+1; j <= N+M; ++j) {
	if (cap[i][j]) --cap[i][j]; // 如果有該貼紙, 保留一個絕對不會交換
	else cap[j][i] = 1; // 如果沒有, cap[j][i]容量為1表示可接受交換一個
	}
	}
	for (int i = N+1; i <= N+M; ++i) // 建立貼紙到T容量為1
	cap[i][T] = 1;
	// Maximum Flow (bfs)
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(1);
	bottleneck[1] = 9999999;
	while (!Q.empty() && !bottleneck[T]) {
	int cur = Q.front(); Q.pop();
	for (int nxt = 1; nxt <= T; ++nxt) {
	if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
	Q.push(nxt);
	pre[nxt] = cur;
	bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
	}
	}
	}
	if (bottleneck[T] == 0) break;
	for (int cur = T; cur != 1; cur = pre[cur]) {
	flow[pre[cur]][cur] += bottleneck[T];
	flow[cur][pre[cur]] -= bottleneck[T];
	}
	result += bottleneck[T];
	}
	// Output
	printf("Case #%d: %d\n", Case++, result);
	}
	}

view raw [UVa] 10779 Collector Problem.cpp hosted with ❤ by GitHub