Google Code Jam 2014 Round 2 C Don't Break The Nile

Nile.cpp

#include <iostream>
#include <vector>
#include <set>

using namespace std;

//  蟻本
const int MAX_V = 10*1024*1024;
struct edge { int to, cap, rev; };

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, int cap)
{
    //printf("%d %d %d\n", from, to, cap);

    edge e;
    e.to = to;
    e.cap = cap;
    e.rev = G[to].size();
    G[from].push_back(e);
    e.to = from;
    e.cap = 0;
    e.rev = G[from].size()-1;
    G[to].push_back(e);
}

int dfs(int v, int t, int f)
{
    if (v==t)return f;
    used[v] = true;
    for(int i=0; i<G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap>0)
        {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t)
{
    int flow = 0;
    for(;;){
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, 0x7fffffff);
        if (f==0) return flow;
        flow += f;
    }
    return -1;
}




int main()
{
    int T;
    cin>>T;

    for (int test=1; test<=T; test++)
    {
        int W, H, B;
        cin>>W>>H>>B;
        vector<int> X0(B), Y0(B), X1(B), Y1(B);
        for (int b=0; b<B; b++)
            cin>>X0[b]>>Y0[b]>>X1[b]>>Y1[b];

        set<int> S;
        S.insert(0);
        S.insert(H);
        S.insert(Y0.begin(), Y0.end());
        for (int i=0; i<B; i++)
            S.insert(Y1[i]+1);
        vector<int> YT(S.begin(), S.end());

        vector<vector<bool> > F(YT.size(), vector<bool>(W));
        for (int b=0; b<B; b++)
        {
            int ys=-1, ye=-1;
            for (int i=0; i<(int)YT.size(); i++)
            {
                if (YT[i]==Y0[b])
                    ys = i;
                if (YT[i]==Y1[b]+1)
                    ye = i;
            }
            if (ys==-1 || ye==-1)
                printf("ERROR 1\n");

            for (int y=ys; y<ye; y++)
            for (int x=X0[b]; x<=X1[b]; x++)
                F[y][x] = true;
        }

        for (int i=0; i<MAX_V; i++)
            G[i].clear();
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        

        int H2 = (int)YT.size()-1;

        fprintf(stderr, "%d\n", H2);

        if (W*H2*2+2 > MAX_V)
            printf("ERROR 2\n");

        for (int y=0; y<H2; y++)
        for (int x=0; x<W; x++)
        if (!F[y][x])
        {
            int p = y*W+x;

            add_edge(p*2, p*2+1, 1);

            for (int d=0; d<4; d++)
            {
                int tx = x + dx[d];
                int ty = y + dy[d];
                if (0<=tx && tx<W &&
                    0<=ty && ty<(int)YT.size()-1 && !F[ty][tx])
                {
                    int q = ty*W+tx;

                    int f = d>=2 ? 1 : YT[y+1]-YT[y];

                    add_edge(p*2+1, q*2, f);
                }
            }
        }

        for (int x=0; x<W; x++)
        {
            if (!F[0][x])
                add_edge(W*H2*2, x*2, 1);
            if (!F[H2-1][x])
                add_edge(((H2-1)*W+x)*2+1, W*H2*2+1, 1);
        }

        int ans = max_flow(W*H2*2, W*H2*2+1);
        printf("Case #%d: %d\n", test, ans);
        fprintf(stderr, "Case #%d: %d\n", test, ans);
    }

    return 0;
}