POJ 2584 T-Shirt Gumbo

題意：
　　以sample input舉例
START 4     -> 4表示有4個人
SM ML LX XT    -> 第一人能穿的衣服Size從S~M，第二人從M~L，...
0 1 1 1 0    -> 衣服S號有0件，M號有1件，L號有1件，X號有1件，T號有0件
END
    求出是否能將衣服分配給所有人。
想法：
    最大流題目，S表示super source，T表示super sink，S到每個人的容量為1，因為每個人只需要一件衣服；每種size的衣服到T的容量為該種size衣服的數量；然後做最大流，並判斷最後的數量是否與人數一樣。

	#include <cstdio>
	#include <string>
	#include <cstring>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int SizeToNum(int N, char ch);
	int cap[30][30], flow[30][30];
	int bottleneck[30], pre[30];
	// 人的編號從0~N-1
	// 衣服size編號從N~N+4
	int main()
	{
	char str[50];
	while (scanf("%s", str) && string(str) != "ENDOFINPUT") {
	int N;
	scanf("%d", &N);
	// Initial
	int S = N+5, // super source
	T = N+6; // super sink
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	// Input & Initial
	for (int i = 0; i < N; ++i) {
	scanf("%s", str);
	for (int j = SizeToNum(N, str[0]); j <= SizeToNum(N, str[1]); ++j)
	cap[i][j] = 1;
	cap[S][i] = 1;
	}
	for (int i = N, m; i < N+5; ++i) {
	scanf("%d", &m);
	cap[i][T] = m;
	}
	scanf("%s"); // END
	// Maximum Flow (bfs)
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(S);
	bottleneck[S] = 999999;
	while (!Q.empty()) {
	int cur = Q.front(); Q.pop();
	for (int nxt = 0; nxt <= N+6; ++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 != S; cur = pre[cur]) {
	flow[pre[cur]][cur] += bottleneck[T];
	flow[cur][pre[cur]] -= bottleneck[T];
	}
	result += bottleneck[T];
	}
	// Analysis & Ouput
	if (result == N) puts("T-shirts rock!");
	else puts("I'd rather not wear a shirt anyway...");
	}
	}
	int SizeToNum(int N, char ch)
	{
	switch (ch) {
	case 'S': return N;
	case 'M': return N+1;
	case 'L': return N+2;
	case 'X': return N+3;
	case 'T': return N+4;
	}
	}

view raw [POJ] 2584 T-Shirt Gumbo.cpp hosted with ❤ by GitHub