UVA 11045 My T-shirt suits me 网络流构图

题意：公司要给志愿者发服装，有N件衣服，分别为N/5套衣服，每套衣服6种型号，有M个志愿者，然后每个志愿者分别可以适应2种型号的衣服，问所给的衣服够多吗。

可以用网络流来做，构图时想一想就行了，汇点和各种衣服的容量为N/5，表示可以发放N/5套衣服，衣服和能穿那种衣服的人的容量为1，表示一件衣服只能让一个人穿，每个人和汇点的容量为1，表示每个人最后只能选择一件衣服。

最后判断最大流是否为M就行了。

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        uva11045.cpp
*  Create Date: 2013-12-07 21:20:31
*  Descripton:  maxFlow 
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int MAXN = 40; const int INF = 0x3c3c3c3c; int mr[MAXN]; // 从源点到i的最小残量 int p[MAXN]; // 更新时i的上流节点 int c[MAXN][MAXN], f[MAXN][MAXN]; // capitar and flow char ch[6][4] = {"XXL", "XL", "L", "M", "S", "XS"}, sz[4]; int maxFlow(int op, int ed, int n) // start, end, num of points { queue
        
          q; memset(f, 0, sizeof(f)); memset(p, 0, sizeof(p)); int F = 0; // total flow // bfs while (1) { memset(mr, 0, sizeof(mr)); q.push(op); mr[op] = INF; // 源点残量 while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < n; v++) if (!mr[v] && c[u][v] > f[u][v]) { p[v] = u; q.push(v); mr[v] = min(mr[u], c[u][v] - f[u][v]); } } if (mr[ed] == 0) return F; // update for (int u = ed; u != op; u = p[u]) { f[u][p[u]] -= mr[ed]; f[p[u]][u] += mr[ed]; } F += mr[ed]; } } int main() { int t; int n, m; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); memset(c, 0, sizeof(c)); for (int i = 1; i <= 6; i++) c[0][i] = n / 6; for (int i = 1; i <= m; i++) { c[6 + i][7 + m] = 1; scanf("%s", sz); for (int j = 0; j < 6; j++) if (!strcmp(sz, ch[j])) { c[j + 1][6 + i] += 1; break; } scanf("%s", sz); for (int j = 0; j < 6; j++) if (!strcmp(sz, ch[j])) { c[j + 1][6 + i] += 1; break; } } int x = maxFlow(0, 7 + m, 8 + m); if (x == m) puts("YES"); else puts("NO"); } return 0; }