HDU 4292 Food(拆點，最大流)

[cpp] 
/*
最大流問題
拆點：增加超級源點和匯點，源點於食物相連，邊的權值為食物最大量；飲料與匯點相連，變得權值為飲料的最大量；
將人拆分成兩個，一個與食物相連，一個與飲料相連，權值可以為1也可以為INF，無影響。
將拆分後的兩個節點相連，邊的權值為1
*/ 
 
#include <cstdio> 
#include <cstring> 
const int nMax = 2007; 
const int INF = 0x3fffffff; 
int N, F, D; 
int NN; 
struct Adj 
{ 
    int v, w; 
    int next; 
    Adj(){} 
    Adj(int v, int w, int next):v(v), w(w), next(next){} 
}adj[100 * nMax]; 
int head[nMax]; 
int cnt; 
int dis[nMax], num[nMax]; 
 
void addEdge(int u, int v, int w) 
{ 
    adj[cnt] = Adj(v, w, head[u]); 
    head[u] = cnt ++; 
    adj[cnt] = Adj(u, 0, head[v]); 
    head[v] = cnt ++; 
} 
 
int min(int a, int b) 
{ 
    return a < b ? a : b; 
} 
 
int dfs(int u, int s, int d, int cost) 
{ 
    if(u == d) return cost; 
    int i; 
    int ans = 0; 
    int _min = NN; 
    for(i = head[u]; i != -1; i = adj[i].next) 
    { 
        int v = adj[i].v; 
        if(adj[i].w) 
        { 
            if(dis[v] + 1 == dis[u]) 
            { 
                int t = dfs(v, s, d, min(adj[i].w, cost)); 
                adj[i].w -= t; 
                adj[i ^ 1].w += t; 
                ans += t; 
                cost -= t; 
                if(dis[s] == NN) return ans; 
                if(!cost) break; 
            } 
            if(_min > dis[v]) 
                _min = dis[v]; 
        } 
    } 
    if(!ans) 
    { 
        if(-- num[dis[u]] == 0) dis[s] = NN; 
        dis[u] = _min + 1; 
        ++ num[dis[u]]; 
    } 
    return ans; 
} 
 
int isap(int s, int d) 
{ 
    memset(dis, 0, sizeof(dis)); 
    memset(num, 0, sizeof(num)); 
    num[0] = NN; 
    int ans = 0; 
    while(dis[s] < NN) 
        ans += dfs(s, s, d, INF); 
    return ans; 
} 
 
int main() 
{ 
    //freopen("e://data.in", "r", stdin); 
    while(scanf("%d%d%d", &N, &F, &D) != EOF) 
    { 
        int i, j; 
        int a; 
        char s[nMax]; 
        memset(head, -1, sizeof(head)); 
        cnt = 0; 
        for(i = 1; i <= F; ++ i)  
        { 
            scanf("%d", &a); 
            addEdge(0, i, a); 
        } 
        for(i = 1; i <= D; ++ i) 
        { 
            scanf("%d", &a); 
            addEdge(F + 2 * N + i, F + 2 * N + D + 1, a); 
        } 
        for(i = 1; i <= N; ++ i) 
        { 
            addEdge(F + i, F + N + i, 1); 
        } 
        for(i = 1; i <= N; ++ i) 
        { 
            scanf("%s", s + 1); 
            for(j = 1; j <= F; ++ j) 
                if(s[j] == 'Y') 
                    addEdge(j, F + i, INF); 
        } 
        for(i = 1; i <= N; ++ i) 
        { 
            scanf("%s", s + 1); 
            for(j = 1; j <= D; ++ j) 
                if(s[j] == 'Y') 
                    addEdge(F + N + i, F + 2 * N + j, INF); 
        } 
        NN = F + 2 * N + D + 2; 
        int ans = isap(0, NN - 1); 
        printf("%d\n", ans); 
    } 
    return 0; 
}