uva 753 - A Plug for UNIX(网络流最大流）uva 753 - A Plug for UNIX(网络流最大流）

题目大意：给出n，有n种插座；给出m，表示有m种电器，给出电器名以及插头的类型；给出k，表示有k种转接器，给出可以桥接的插头和插座。 问说最少有多少个电器没有插座用。

解题思路：网络流，问题是怎样建图。我的做法是将0做为起点s，与所有的插座建立一条边，容量为1，然后再将所有的电器与终点t建立一条边，容量为1；然后将转接器所桥接的插头与插座的类型间建立一条边，容量为1；注意图中的点表示的是一类插头或者插座，即有相同的情况时边的容量与插头/座的数量相同。然后就是最大流的增广路算法。

#include   
#include   
#include   
  
using namespace std;  
  
#define min(a,b) (a)<(b) (a):(b)  
#define max(a,b) (a)>(b) (a):(b)  
  
const int N = 1005;  
const int INF = 1 << 20;  
  
int n, m, k, tmp, t[N];  
int f[N][N], g[N][N], rec[N];  
char name[N][N];  
  
int find(char *ch) {  
    for (int i = 0; i < tmp; i++) {  
        if (strcmp(ch, name[i]) == 0) return i;  
    }  
  
    strcpy(name[tmp], ch);  
    return tmp++;  
}  
  
void init() {  
  
    tmp = 1;  
    memset(g, 0, sizeof(g));  
    memset(f, 0, sizeof(f));  
    memset(name, 0, sizeof(name));  
  
    char ch[N], na[N];  
  
    scanf("%d", &n);  
    for (int i = 0; i < n; i++) {  
  
        scanf("%s", ch);  
        int p = find(ch);  
        g[0][p]++;  
    }  
  
    scanf("%d", &m);  
    for (int i = 0; i < m; i++) {  
  
        scanf("%s%s", na, ch);  
        int p = find(ch);  
        rec[i] = p;  
    }  
  
    scanf("%d", &k);  
    for (int i = 0; i < k; i++) {  
  
        scanf("%s%s", ch, na);  
        int p = find(ch), q= find(na);  
        g[q][p] = INF;  
    }  
}  
  
int solve() {  
    queue





 q;  
    int ans = 0;  
  
    for (int i = 0; i < m; i++)  
        g[rec[i]][tmp]++;  
      
    while (1) {  
  
        int b = 0;  
        memset(t, 0, sizeof(t));  
        memset(rec, 0, sizeof(rec));  
  
        q.push(b);  
        t[b] = INF;  
  
        while (!q.empty()) {  
  
            b = q.front(), q.pop();  
  
            for (int i = 1; i <= tmp; i++) {  
  
                if (!t[i] && g[b][i] > f[b][i]) {  
  
                    int cur = min(g[b][i] - f[b][i], t[b]);  
                    if (cur > t[i]) {  
  
                        t[i] = cur;  
                        rec[i] = b;  
                        q.push(i);  
                    }  
                }  
            }  
        }  
  
        if (t[tmp] == 0) break;  
        ans += t[tmp];  
        for (int i = tmp; i; i = rec[i]) {  
            f[rec[i]][i] += t[tmp];  
            f[i][rec[i]] -= t[tmp];  
        }  
    }  
  
    return ans;  
}  
  
int main () {  
    int cas;  
    scanf("%d", &cas);  
    while (cas--) {  
  
        init();  
        printf("%d\n", m - solve());  
  
        if (cas) printf("\n");  
    }  
    return 0;  
}