程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1087 A Plug for UNIX （網絡最大流）

POJ 1087 A Plug for UNIX （網絡最大流）

編輯：C++入門知識

POJ 1087 A Plug for UNIX （網絡最大流）

POJ 1087 A Plug for UNIX

鏈接：http://poj.org/problem?id=1087
題意：有n（1≤n≤100）個插座，每個插座用一個數字字母式字符串描述（至多有24 個字符）。有m（1≤m≤100）個設備，每個設備有名稱，以及它使用的插頭的名稱；插頭的名稱跟它所使用的插座的名稱是一樣的；設備名稱是一個至多包含24 個字母數字式字符的字符串；任何兩個設備的名稱都不同；有k（1≤k≤100）個轉換器，每個轉換器能將插座轉換成插頭。
樣例：

4 
A 
B 
C 
D 
5 
laptop B 
phone C 
pager B 
clock B 
comb X 
3 
B X 
X A 
X D

思路：建立一個匯點，每個插座和匯點連邊，流量代表該種插座的個數。建立一個源點，源點和每個設備連邊，流量為1。每個轉換器將兩個插座連邊，流量為INF。然後求最大流。答案就是設備的個數減去最大流。
細節：這道題在建圖的時候比較惡心。需要注意的是，在m個設備和插座以及k個轉換器的數據中，可能有之前沒有出現過的設備。所以必須將插座的信息存起來，可以用map來存插座對應的點。
代碼：

/*
ID: [email protected]
PROG:
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 610;
const int maxm = 2000000;
int m, k;
struct node {
    int v;    // vertex
    int cap;    // capacity
    int flow;   // current flow in this arc
    int nxt;
} e[maxm * 2];
int g[maxn], cnt;
int st, ed, n;
void add(int u, int v, int c) {
    e[++cnt].v = v;
    e[cnt].cap = c;
    e[cnt].flow = 0;
    e[cnt].nxt = g[u];
    g[u] = cnt;

    e[++cnt].v = u;
    e[cnt].cap = 0;
    e[cnt].flow = 0;
    e[cnt].nxt = g[v];
    g[v] = cnt;
}
map mp;
map :: iterator it;
void init() {
    mem(g, 0);
    cnt = 1;
    mp.clear();
    scanf("%d", &n);
    char str[25];
    ed = 0;
    int tot = 1, has[111] = {0};
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        string ss(str);
        int now;
        if (mp[ss] == 0) {
            mp[ss] = tot;
            now = tot++;
        } else now = mp[ss];
        has[now]++;
    }
    for (int i = 1; i < tot; i++) add(i, ed, has[i]);
    scanf("%d", &m);
    char s[25];
    vector v;
    for (int i = 0; i < m; i++) {
        scanf("%s%s", str, s);
        v.pb(tot);
        if (mp[s]) add(tot++, mp[s], 1);
        else {
            mp[s] = tot + 1;
            add(tot, tot + 1, 1);
            tot += 2;
        }
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%s%s", str, s);
        if (mp[str] == 0) mp[str] = tot++;
        if (mp[s] == 0) mp[s] = tot++;
        add(mp[str], mp[s], INF);
    }
    st = tot;
    for (int i = 0; i < v.size(); i++) add(st, v[i], 1);
    n = tot + 3;
}

int dist[maxn], numbs[maxn], q[maxn];
void rev_bfs() {
    int font = 0, rear = 1;
    for (int i = 0; i <= n; i++) { //n為總點數
        dist[i] = maxn;
        numbs[i] = 0;
    }
    q[font] = ed;
    dist[ed] = 0;
    numbs[0] = 1;
    while(font != rear) {
        int u = q[font++];
        for (int i = g[u]; i; i = e[i].nxt) {
            if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue;
            dist[e[i].v] = dist[u] + 1;
            ++numbs[dist[e[i].v]];
            q[rear++] = e[i].v;
        }
    }
}
int maxflow() {
    rev_bfs();
    int u, totalflow = 0;
    int curg[maxn], revpath[maxn];
    for(int i = 0; i <= n; ++i) curg[i] = g[i];
    u = st;
    while(dist[st] < n) {
        if(u == ed) {   // find an augmenting path
            int augflow = INF;
            for(int i = st; i != ed; i = e[curg[i]].v)
                augflow = min(augflow, e[curg[i]].cap);
            for(int i = st; i != ed; i = e[curg[i]].v) {
                e[curg[i]].cap -= augflow;
                e[curg[i] ^ 1].cap += augflow;
                e[curg[i]].flow += augflow;
                e[curg[i] ^ 1].flow -= augflow;
            }
            totalflow += augflow;
            u = st;
        }
        int i;
        for(i = curg[u]; i; i = e[i].nxt)
            if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
        if(i) {   // find an admissible arc, then Advance
            curg[u] = i;
            revpath[e[i].v] = i ^ 1;
            u = e[i].v;
        } else {    // no admissible arc, then relabel this vertex
            if(0 == (--numbs[dist[u]])) break;    // GAP cut, Important!
            curg[u] = g[u];
            int mindist = n;
            for(int j = g[u]; j; j = e[j].nxt)
                if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
            dist[u] = mindist + 1;
            ++numbs[dist[u]];
            if(u != st)
                u = e[revpath[u]].v;    // Backtrack
        }
    }
    return totalflow;
}

int main () {
    init();
    printf("%d\n", m - maxflow());
    return 0;
}