poj 1087 A Plug for UNIX（最大流基础）

题意：
。。。
思路：
这也是一道二分匹配，不过用最大流解法简单了很多。
建图时注意，适配器是无限的，所以容量为inf。

const int inf = INT_MAX/2;
const int Maxn = 100000;
const int MaxV = 700;
struct Edge {
    int to, cap, rev;
};

vector<Edge> G[MaxV+5];
int level[MaxV+5], iter[MaxV+5]; // 距离标号，当前边

// 在残量网络里面加边
void add_edge(int from, int to, int cap) {
    G[from].push_back( (Edge){to, cap, G[to].size()} );
    G[to].push_back( (Edge){from, 0, G[from].size()-1} );
}

// bfs 构建层次
void bfs(int s) {
    memset(level, -1, sizeof(level));
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();q.pop();
        int sz = G[u].size();
        for (int i=0;i<sz;++i) {
            Edge &e = G[u][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
            }
        }
    }
}

int dfs(int x, int t, int f) {
    //cout << "go " << x << endl;
    if (x == t || f == 0) return f;
    int flow = 0, sz = G[x].size();
    for (int &i = iter[x]; i<sz;++i) {
        Edge &e = G[x][i];
        if (e.cap > 0 && level[x] < level[e.to]) {
            int d = dfs(e.to, t, min (f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                flow += d;
                f -= d;
                if (!f) break;
            }
        }
    }
    return flow;
}

int max_flow(int s, int t) {
    int flow = 0;
    for (;;) {
        bfs (s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        flow += dfs(s, t, inf);
    }
    return flow;
}

int n, m, k, tot;

map<string, int> id;

// device i: i+n
// receptacle i: i
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    SPEED_UP
    cin >> n;
    rep(i, 1, n) {
        string tmp;cin >> tmp;id[tmp] = i;
    }
    cin >> m;
    tot = n+m;
    rep(i, 1, m) {
        string x, y;
        cin >> x >> y;
        if (!id.count(y)) {++tot;id[y] = tot;}
        add_edge(i+n, id[y], 1);
    }
    cin >> k;
    rep(i, 1, k) {
        string x, y;
        cin >> x >> y;
        if (!id.count(x)) {++tot;id[x] = tot;}
        if (!id.count(y)) {++tot;id[y] = tot;}
        add_edge(id[x], id[y], inf);
    }
    //for (auto i:id) {
    // cout << i.first << ' ' << i.second << endl;
    //}
    // 超级源点0
    rep(i, 1, m) add_edge(0, i+n, 1);

    // 拆点
    rep(i, 1, n) add_edge(i, i+tot, 1);

    // 超级汇点 tot+1
    rep(i, 1, n) add_edge(i+tot, tot+1, 1);

    int _max = max_flow(0, tot+1);
    cout << m - _max << endl;
    return 0;
}