题意：(XXL, XL, L, M , S, or XS)每个尺码有若干件，需要分发给m个志愿者。告诉你每个志愿者有两个合适的尺码。问你是否每个志愿者都能找到合适的衣服？
思路：其实是二分匹配问题，这两天在学网络流就转化了一下，首先在二分图的学生节点前各加一个指向他流量为1的边再用一个源点指向连接这条边的点，在衣服节点后加一个被指向流量为衣服件数的边。再在这些边后面增加一个汇点。这样图建好了，套一下模版就OK。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <utility> 10 #define LEN 210 11 #define ll long long 12 #define INF 0x3f3f3f3f 13 #define eps 1E-6 14 15 using namespace std; 16 17 int v, m, n, cap[LEN][LEN]; 18 19 int ch(char str[]){ 20 if(strcmp(str, "XS")==0)return 0; 21 if(strcmp(str, "S")==0)return 1; 22 if(strcmp(str, "M")==0)return 2; 23 if(strcmp(str, "L")==0)return 3; 24 if(strcmp(str, "XL")==0)return 4; 25 if(strcmp(str, "XXL")==0)return 5; 26 } 27 28 int EK(int s, int t) 29 { 30 int f, flow[LEN][LEN], a[LEN], p[LEN]; 31 queue<int> q; 32 memset(flow, 0, sizeof flow); 33 f = 0; 34 while(1){ 35 memset(a, 0, sizeof a); 36 a[s] = INF; 37 q.push(s); 38 while(!q.empty()){ 39 int u = q.front(); q.pop(); 40 for(int v=0; v<n; v++){ 41 if(!a[v] && cap[u][v]>flow[u][v]){ 42 p[v] = u; 43 q.push(v); 44 a[v] = min(a[u], cap[u][v]-flow[u][v]); 45 } 46 } 47 } 48 if(a[t] == 0)break; 49 for(int u=t; u!=s; u = p[u]){ 50 flow[p[u]][u]+=a[t]; 51 flow[u][p[u]]-=a[t]; 52 } 53 f+=a[t]; 54 } 55 return f; 56 } 57 58 int main() 59 { 60 // freopen("in.txt", "r", stdin); 61 62 char str[20]; 63 int T; 64 scanf("%d", &T); 65 while(T--){ 66 scanf("%d%d", &v, &m); 67 memset(cap, 0, sizeof cap); 68 for(int i=0; i<m; i++){ 69 cin >> str; 70 cap[i][m+ch(str)] = 1; 71 cin >> str; 72 cap[i][m+ch(str)] = 1; 73 } 74 n = m+6; 75 for(int i=0; i<6; i++){ 76 cap[m+i][n++] = v/6; 77 } 78 for(int i=0; i<m; i++){ 79 cap[n++][i] = 1; 80 } 81 for(int i=m+12; i<2*m+12; i++){ 82 cap[n][i] = INF; 83 } 84 for(int i=m+6; i<m+12; i++){ 85 cap[i][n+1] = INF; 86 } 87 n+=2; 88 int ans = EK(n-2, n-1); 89 if(m==ans)cout << "YES" << endl; 90 else cout << "NO" << endl; 91 } 92 return 0; 93 }