有5种T-shirt， n个人， 每个人可以接受某些种T-shirt， 每种T-shirt的数量已知， 问每个人能否都穿上自己能接受的T-shirt。
源点向每种T-shirt连边， 权值为个数。 将人拆成两个点u和u'， T-shirt向u连边， 权值为1， u向u'连边， 权值为1， u'向汇点连边， 权值为inf。 跑一遍最大流， 看结果是否等于n就可以了。
很简单的题写了好久orz....代码能力太差了。
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
const int inf = ;
const int maxn = 1e4+;
int head[maxn*], s, t, num, q[maxn*], dis[maxn];
struct node
{
int to, nextt, c;
}e[maxn*];
void init() {
mem1(head);
num = ;
}
void add(int u, int v, int c) {
e[num].to = v; e[num].nextt = head[u]; e[num].c = c; head[u] = num++;
e[num].to = u; e[num].nextt = head[v]; e[num].c = ; head[v] = num++;
}
int bfs() {
int u, v, st = , ed = ;
mem(dis);
dis[s] = ;
q[ed++] = s;
while(st<ed) {
u = q[st++];
for(int i = head[u]; ~i; i = e[i].nextt) {
v = e[i].to;
if(e[i].c&&!dis[v]) {
dis[v] = dis[u]+;
if(v == t)
return ;
q[ed++] = v;
}
}
}
return ;
}
int dfs(int u, int limit) {
if(u == t)
return limit;
int cost = ;
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to;
if(e[i].c&&dis[u] == dis[v]-) {
int tmp = dfs(v, min(limit-cost, e[i].c));
if(tmp>) {
e[i].c -= tmp;
e[i^].c += tmp;
cost += tmp;
if(cost == limit)
break;
} else {
dis[v] = -;
}
}
}
return cost;
}
int dinic() {
int ans = ;
while(bfs()) {
ans += dfs(s, inf);
}
return ans;
}
map <char, int> m;
int val[];
char c[][];
int main()
{
m['S'] = , m['M'] = , m['L'] = , m['X'] = , m['T'] = ;
string str;
int n;
while(cin>>str) {
init();
if(str == "ENDOFINPUT")
break;
scanf("%d", &n);
s = , t = *n++;
for(int i = ; i<=n; i++) {
scanf("%s", c[i]);
}
for(int i = ; i<=; i++) {
scanf("%d", &val[i]);
}
for(int i = ; i<=; i++) {
add(s, i, val[i]);
}
for(int i = ; i<=n; i++) {
if(c[i][] == c[i][]) {
add(m[c[i][]], i+, );
} else {
for(int j = m[c[i][]]; j<=m[c[i][]]; j++) {
add(j, i+, );
}
}
}
for(int i = ; i<=n; i++) {
add(i+, i++n, );
add(i++n, t, inf);
}
cin>>str;
int ans = dinic();
if(ans == n) {
cout<<"T-shirts rock!"<<endl;
} else {
cout<<"I'd rather not wear a shirt anyway..."<<endl;
}
}
}