UVA 753 A Plug for UNIX 网络流插头匹配

题目：有n个不同插口，每种插口有一个名字，现在要为m台设备安排插头，每台设备对应一种插口，当然，你也可以去商店买插口适配器来用，商店有k种适配器，每种适配器能够接受一种的插头，并插在另一种插口上，适配器随便你买。现在问你这样还有多少太设备没法插上电...

这题的构图还算不是很复杂，但是我做了半天...因为没有看到适配器可以有多个，我以为只有一个。太坑。

建图为超源点->设备->插头->超汇点，插头间的转换是INF，其他都是1。

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        uva753.cpp
*  Create Date: 2013-12-07 21:55:12
*  Descripton:  max flow 
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           using namespace std; const int MAXN = 310; const int INF = 0x3c3c3c3c; string str; map
          
            rs, dv; int mr[MAXN]; // 从源点到i的最小残量 int p[MAXN]; // 更新时i的上流节点 int c[MAXN][MAXN], f[MAXN][MAXN]; // capitar and flow 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, k, did, rid, adt; // 多出来的接口数量 scanf("%d", &t); while (t--) { rs.clear(); dv.clear(); memset(c, 0, sizeof(c)); adt = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { cin >> str; rs[str] = i; } scanf("%d", &m); for (int i = 1; i <= m; i++) { // get the id of divice cin >> str; if ((did = dv[str]) == 0) did = (dv[str] = i); c[0][did] += 1; // get the id of receptacle cin >> str; if ((rid = rs[str]) == 0) { adt++; rid = (rs[str] = n + adt); } c[did][rid + m] += 1; //c[rid + m][did] += 1; } // 建立超级汇点 for (int i = m + 1; i <= m + n; i++) c[i][m + n + adt + 1] += 1; scanf("%d", &k); for (int i = 0; i < k; i++) { cin >> str; rid = rs[str]; cin >> str; c[m + rid][m + rs[str]] += INF; } int ans = maxFlow(0, m + n + adt + 1, m + n + adt + 2); printf("%d\n", m - ans); if (t) puts(""); } return 0; }

UVA 753 A Plug for UNIX 网络流 插头匹配