学步园

HYSBZ_1001

    建好图之后求最小割即可。

#include<stdio.h>
#include<string.h>
#define MAXD 1000100
#define MAXM 6000600
#define INF 1000000000
int N, M, T, e, first[MAXD], next[MAXM], u[MAXM], v[MAXM], flow[MAXM];
int q[MAXD], d[MAXD], work[MAXD], s[MAXD];
void add(int a, int b, int f)
{
    u[e] = a;
    v[e] = b;
    flow[e] = f;
    next[e] = first[a];
    first[a] = e;
    e ++;
}
void init()
{
int i, j, a, b, f;
    T = N * M - 1;
    e = 0;
for(i = 0; i <= T; i ++)
        first[i] = -1;
for(i = 0; i < N; i ++)
for(j = 1; j < M; j ++)
        {
            scanf("%d", &f);
            a = i * M + j - 1;
            b = i * M + j;
            add(a, b, f);
            add(b, a, f);
        }
for(i = 1; i < N; i ++)
for(j = 0; j < M; j ++)
        {
            scanf("%d", &f);
            a = (i - 1) * M + j;
            b = i * M + j;
            add(a, b, f);
            add(b, a, f);
        }
for(i = 1; i < N; i ++)
for(j = 1; j < M; j ++)
        {
            scanf("%d", &f);
            a = (i - 1) * M + j - 1;
            b = i * M + j;
            add(a, b, f);
            add(b, a, f);
        }
}
int bfs()
{
int i, j, rear;
for(i = 1; i <= T; i ++)
        d[i] = -1;
    d[0] = 0;
    rear = 0;
    q[rear ++] = 0;
for(i = 0; i < rear ; i ++)
for(j = first[q[i]]; j != -1; j = next[j])
if(flow[j] && d[v[j]] == -1)
            {
                d[v[j]] = d[q[i]] + 1;
if(v[j] == T)
return 1;
                q[rear ++] = v[j];
            }
return 0;
}
int dinic()
{
int i, j, cur, r, res = 0;
while(bfs())
    {
        r = 0;
        cur = 0;
for(i = 0; i <= T; i ++)
            work[i] = first[i];
for(;;)
        {
if(cur == T)
            {
int a = INF, minr = r;
for(i = 0; i < r; i ++)
if(flow[s[i]] < a)
                    {
                        a = flow[s[i]];
                        minr = i;
                    }
for(i = 0; i < r; i ++)
                {
                    flow[s[i]] -= a;
                    flow[s[i] ^ 1] += a;
                }
                r = minr;
                cur = u[s[r]];
                res += a;
            }
for(i = work[cur]; i != -1; i = next[i])
if(flow[i] && d[v[i]] == d[cur] + 1)
break;
            work[cur] = i;
if(i != -1)
            {
                s[r ++] = i;
                cur = v[i];
            }
else
            {
                d[cur] = -1;
if(r == 0)
break;
                r --;
                cur = u[s[r]];
            }
        }
    }
return res;
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
    {
        init();
int res = dinic();
        printf("%d\n", res);
    }
return 0;
}