uva 11045(最大流)

心已赠人 2021-12-24 14:39 186阅读 0赞

题意：(XXL, XL, L, M , S, or XS)每个尺码有若干件，需要分发给m个志愿者。告诉你每个志愿者有两个合适的尺码。问你是否每个志愿者都能找到合适的衣服？

思路：其实是二分匹配问题，这两天在学网络流就转化了一下，首先在二分图的学生节点前各加一个指向他流量为1的边再用一个源点指向连接这条边的点，在衣服节点后加一个被指向流量为衣服件数的边。再在这些边后面增加一个汇点。这样图建好了，套一下模版就OK。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/shu-xiaohao/p/3476101.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/69595848f3f642ddbaccf22fd03f44cf.png