HDU 4292 Food(最大流再优化?)

Description

与POJ 3281 Dining相似，人、食物、饮料，不同的是现在食物、饮料数目不止一份

最大流建图：

1. 人 拆点(每人匹配一食物一饮料)
2. 食物与人之间的容量设为1或INF都行

优化

1. 字符串用scanf("%s", str)比循环getchar快？
2. main函数调用其他函数耗时？add里写两份
3. BFS出口改了……
4. DFS形式改了，添加了一句deep[s] = -1;
5. 犯的大错误：

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);

const int N = 805;

int nn, ff, dd, maxflow, deep[N];

struct edge
{
    int to, w, pre;
} a[200005];

int cnt = -1;
int head[N], start, over, q[N], fro, bac;

void add(int from, int to, int w)
{
    a[++cnt].to = to;
    a[cnt].pre = head[from];
    a[cnt].w = w;
    head[from] = cnt;
    a[++cnt].to = from;
    a[cnt].pre = head[to];
    a[cnt].w = 0;
    head[to] = cnt;
}

bool bfs()
{
    memset(deep, -1, sizeof(deep));
    fro = bac = 0;
    q[bac++] = start, deep[start] = 0;

    while(fro < bac)
    {
        int first = q[fro++];
//        if(first == over)
//            return true;
        for(int i = head[first]; i != -1; i = a[i].pre)
        {
            int v = a[i].to;
            if(deep[v] < 0 && a[i].w > 0)
            {
                deep[v] = deep[first] + 1;
                q[bac++] = v;
            }
        }
    }
//    return false;
    return deep[over] > 0;
}

int DFS(int s, int cap)
{
    if(s == over)
        return cap;

    int f;
    for(int i = head[s]; i != -1; i = a[i].pre)
    {
        int to = a[i].to;
        if(a[i].w > 0 && deep[to] == deep[s] + 1 && 
                   (f = DFS(to, min(cap, a[i].w))) )
        {
            a[i].w -= f;
            a[i ^ 1].w += f;
            return f;
        }
    }
    deep[s] = -1;
    return 0;
}


void Dinic()
{
    int temp;
    while(bfs())
        while((temp = DFS(start, INF)) > 0)
            maxflow += temp;
}

int main()
{
    while(scanf("%d%d%d", &nn, &ff, &dd) != EOF)
    {
        memset(head, -1, sizeof(head));
        int tem;
        cnt = -1, maxflow = start = 0;
        over = 1 + dd + 2 * nn + ff;
        for(int i = 1; i <= ff; ++i)
        {
            scanf("%d", &tem);
            add(start, i, tem);
        }
        for(int i = 1; i <= nn; ++i)
            add(i + ff, i + nn + ff, 1);
        for(int i = 1; i <= dd; ++i)
        {
            scanf("%d", &tem);
            add(i + 2 * nn + ff, over, tem);
        }
        char str[805];
        for(int i = 1; i <= nn; ++i)
        {
            scanf("%s", str);
            for(int j = 0; j < ff; ++j)
                if(str[j] == 'Y')
                    add(j + 1, i + ff, 1);
        }
        for(int i = 1; i <= nn; ++i)
        {
            scanf("%s", str);
            for(int j = 0; j < dd; ++j)
                if(str[j] == 'Y')
                    add(i + nn + ff, j + 1 + 2 * nn + ff, 1);
        }
        Dinic();
        cout << maxflow << '\n';
    }
    return 0;
}