#POJ 2584 T-Shirt Gumbo (最大流)

T-Shirt Gumbo

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3975		Accepted: 1880

Description

Boudreaux and Thibodeaux are student volunteers for this year's ACM South Central Region's programming contest. One of their duties is to distribute the contest T-shirts to arriving teams. The T-shirts had to be ordered in advance using an educated guess as to how many shirts of each size should be needed. Now it falls to Boudreaux and Thibodeaux to determine if they can hand out T-shirts to all the contestants in a way that makes everyone happy.

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 4 components:

1. Start line - A single line:
   START X
   
   where (1 <= X <= 20) is the number of contestants demanding shirts.
2. Tolerance line - A single line containing X space-separated pairs of letters indicating the size tolerances of each contestant. Valid size letters are S - small, M - medium, L - large, X - extra large, T - extra extra large. Each letter pair will indicate the range of sizes that will satisfy a particular contestant. The pair will begin with the smallest size the contestant will accept and end with the largest. For example:
   MX
   
   would indicate a contestant that would accept a medium, large, or extra large T-shirt. If a contestant is very picky, both letters in the pair may be the same.
3. Inventory line - A single line:
   S M L X T
   
   indicating the number of each size shirt in Boudreaux and Thibodeaux's inventory. These values will be between 0 and 20 inclusive.
4. End line - A single line:
   END

After the last data set, there will be a single line:
ENDOFINPUT
 

Output

For each data set, there will be exactly one line of output. This line will reflect the attitude of the contestants after the T-shirts are distributed. If all the contestants were satisfied, output:

T-shirts rock!

Otherwise, output:
I'd rather not wear a shirt anyway...
 

Sample Input

START 1
ST
0 0 1 0 0
END
START 2
SS TT
0 0 1 0 0
END
START 4
SM ML LX XT
0 1 1 1 0
END
ENDOFINPUT

Sample Output

T-shirts rock!
I'd rather not wear a shirt anyway...
I'd rather not wear a shirt anyway...

题目大意 ： 有N个人， 想穿一定范围大小的衣服， 没件衣服各有i个， 问是否所有人都能穿到合适的衣服

思路 ： 源点为 0 ， 衣服大小从1 到 5， 人 从 5到 5 + N， 汇点为 6 + N， 源点到衣服之间有一条流量为该衣服数量的边， 衣服到可以穿这件衣服的人之间有流量为1的边， 每个人到汇点有流量为1的边， 跑一遍最大流判断是否满流即可

Accepted code

#include<iostream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

#define sc scanf
#define ls rt << 1
#define rs ls | 1
#define Min(x, y) x = min(x, y)
#define Max(x, y) x = max(x, y)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define MEM(x, b) memset(x, b, sizeof(x))
#define lowbit(x) ((x) & (-x))
#define P2(x) ((x) * (x))

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }

struct Edge
{
	int v, w, next;
}e[MAXN << 1];
int head[MAXN], n, m, cnt, T, X;
int dep[MAXN], cur[MAXN], sp, tp;
bool vis[MAXN];
string line;
void init() {
	MEM(head, -1); MEM(vis, 0);
	cnt = 0;
}
int swap_(char a) {
	if (a == 'S') return 1;
	else if (a == 'M') return 2;
	else if (a == 'L') return 3;
	else if (a == 'X') return 4;
	else return 5;
}
void add(int from, int to, int w) {
	e[cnt].v = to; e[cnt].w = w;
	e[cnt].next = head[from]; head[from] = cnt++;

	e[cnt].v = from; e[cnt].w = 0;
	e[cnt].next = head[to]; head[to] = cnt++;
}
bool bfs() {
	queue <int> q; MEM(dep, 0);
	dep[sp] = 1, q.push(sp);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = head[now]; i != -1; i = e[i].next) {
			int vi = e[i].v;
			if (!dep[vi] && e[i].w) {
				dep[vi] = dep[now] + 1;
				q.push(vi);
			}
		}
	}
	if (dep[tp]) return true;
	else return false;
}
int dfs(int x, int dist) {
	if (x == tp || dist == 0) return dist;
	int res = 0, r;
	for (int &i = cur[x]; i != -1; i = e[i].next) {
		int vi = e[i].v;
		if (dep[vi] == dep[x] + 1 && e[i].w) {
			r = dfs(vi, min(e[i].w, dist - res));
			if (r > 0) {
				e[i].w -= r;
				e[i ^ 1].w += r;
				res += r;
				if (res == dist) return dist;
			}
		}
	}
	if (!res) dep[x] = 0;
	return res;
}
int dinic() {
	int flow = 0, ans;
	while (bfs()) {
		for (int i = sp; i <= tp; i++) cur[i] = head[i];
		flow += dfs(sp, INF);
	}
	return flow;
}

int main()
{
	while (cin >> line && line != "ENDOFINPUT") {
		sc("%d", &n); init(); 
		sp = 0, tp = 6 + n;
		for (int i = 1; i <= n; i++) {
			cin >> line;
			add(5 + i, tp, 1);
			for (int j = swap_(line[0]); j <= swap_(line[1]); j++)
				add(j, 5 + i, 1);
		}
		for (int i = 1; i <= 5; i++) {
			int tmp; sc("%d", &tmp);
			add(sp, i, tmp); 
		}
		cin >> line;
		int ans = dinic();
		if (ans >= n) cout << "T-shirts rock!" << endl;
		else cout << "I'd rather not wear a shirt anyway..." << endl;
	}
	return 0;
}