poj1087（A Plug for UNIX）解题报告

时间：2010-12-23 来源：myjfm

1、在一个会议室里有n种插座，每种插座一个；

2、每个插座只能插一种以及一个电器（或者适配器）；

3、有m个电器，每个电器有一个插头需要插在相应一种插座上；

4、不是所有电器都能在会议室找到相应插座；

5、有k种适配器，每种适配器可以有无限多数量；

6、每种适配器(a, b)可以把b类插座变为a类插座；

7、问最后有多少个电器无法使用。

本题可以用最大流或者二分图做。

下面讲解最大流：

1、各个电器各自为一个节点，和源点（不存在，自己构造）相连，且源点到电器的容量为1。

2、将室内已有的插座各自为一个节点，和汇点（不存在，自己构造）相连，且到汇点的容量为1。

3、将电器到其应该插的插座类型的点做边，且容量为1。

4、将适配器(a, b)从a点到b点做边，且边的容量为INF。

需要注意，在输入电器以及输入适配器的过程中，如果遇到室内没有的插座类型，则需要在图中添加新的节点。

可根据下图理解：

建图完成之后就是裸最大流，利用Edmonds-Karp算法即可得到图中的最大流。这个最大流的值就是最多有多少电器可以接入。因此用电器的数量减去最大流的值即是要求的结果。

代码如下：

最大流 Edmonds-Karp算法

  1 #include <map>
  2 #include <queue>
  3 #include <string>
  4 #include <cstdio>
  5 #include <cstdlib>
  6  using namespace std;
  7 
  8  const int INF = 0x7fffffff;
  9 const int MAX = 475;
 10 
 11 int c[MAX][MAX], pre[MAX], delta[MAX];
 12 map<string, int> hash;
 13 
 14 int edmonds_karp(int s, int t, int n);
 15 int bfs(int s, int t, int n);
 16 
 17 int main()
 18 {
 19     char strtmp1[30];
 20     char strtmp2[30];
 21     /* l:室内插座数量；
 22      * m:电器的数量;
 23      * n:适配器种类数;
 24      */
 25     int l, m, n;
 26     /* s:网络流中的源;
 27      * t:网络流中的汇;
 28      */
 29     int i, s = 1, t = 2;
 30     /* node_num:记录网络图中节点总数量 */
 31     int node_num = 3;
 32     memset(c, 0, sizeof(c));
 33 
 34     scanf("%d", &l);
 35     
 36     for (i = 0; i < l; ++i)
 37     {
 38         scanf("%s", strtmp1);
 39         hash[strtmp1] = node_num;
 40         /* 室内已有插座到汇点的容量为1 */
 41         c[node_num++][t] = 1;
 42     }
 43 
 44     scanf("%d", &m);
 45 
 46     for (i = 0; i < m; ++i)
 47     {
 48         scanf("%s%s", strtmp1, strtmp2);
 49         hash[strtmp1] = node_num;
 50         /* 源点到所有电器的容量为1 */
 51         c[s][node_num++] = 1;
 52 
 53         /* 如果电器所需要的插座类型在室内根本不存在，则创造新节点 */
 54         if (hash.count(strtmp2) == 0)
 55         {
 56             hash[strtmp2] = node_num++;
 57         }
 58 
 59         /* 从电器到其所需要的插座类型的容量为1 */
 60         c[hash[strtmp1]][hash[strtmp2]] = 1;
 61     }
 62 
 63     scanf("%d", &n);
 64 
 65     for (i = 0; i < n; ++i)
 66     {
 67         scanf("%s %s", strtmp1, strtmp2);
 68 
 69         /* 如果适配器中出现新类型的插座则同样创造新节点 */
 70         if (hash.count(strtmp1) == 0)
 71         {
 72             hash[strtmp1] = node_num++;
 73         }
 74 
 75         if (hash.count(strtmp2) == 0)
 76         {
 77             hash[strtmp2] = node_num++;
 78         }
 79 
 80         /* 从适配器到相应插座的容量为INF */
 81         c[hash[strtmp1]][hash[strtmp2]] = INF;
 82     }
 83 
 84     printf("%d\n", m - edmonds_karp(s, t, node_num));
 85 
 86     return 0;
 87 }
 88 
 89 int edmonds_karp(int s, int t, int n)
 90 {
 91     int i, ans = 0;
 92 
 93     while (bfs(s, t, n))
 94     {
 95         for (i = t; i != s; i = pre[i])
 96         {
 97             c[pre[i]][i] -= delta[t];
 98             c[i][pre[i]] += delta[t];
 99         }
100 
101         ans += delta[t];
102     }
103 
104     return ans;
105 }
106 
107 int bfs(int s, int t, int n)
108 {
109     int i;
110     queue<int> q;
111     memset(pre, 0, sizeof(pre));
112     memset(delta, 0, sizeof(delta));
113     q.push(s);
114     delta[s] = INF;
115 
116     while (!q.empty())
117     {
118         int cur = q.front();
119         q.pop();
120 
121         for (i = 0; i < n; ++i)
122         {
123             if (delta[i] == 0 && c[cur][i] > 0)
124             {
125                 delta[i] = delta[cur] > c[cur][i] ? c[cur][i] : delta[cur];
126                 pre[i] = cur;
127                 q.push(i);
128             }
129         }
130     }
131 
132     if (delta[t] == 0)
133     {
134         return 0;
135     }
136     
137     return 1;
138 }