Golden Eggs HDU

Golden Eggs

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 673 Accepted Submission(s): 400

Problem Description

There is a grid with N rows and M columns. In each cell you can choose to put a golden or silver egg in it, or just leave it empty. If you put an egg in the cell, you will get some points which depends on the color of the egg. But for every pair of adjacent eggs with the same color, you lose G points if there are golden and lose S points otherwise. Two eggs are adjacent if and only if there are in the two cells which share an edge. Try to make your points as high as possible.

Input

The first line contains an integer T indicating the number of test cases.
There are four integers N, M, G and S in the first line of each test case. Then 2*N lines follows, each line contains M integers. The j-th integer of the i-th line Aij indicates the points you will get if there is a golden egg in the cell(i,j). The j-th integer of the (i+N)-th line Bij indicates the points you will get if there is a silver egg in the cell(i,j).

Technical Specification
1. 1 <= T <= 20
2. 1 <= N,M <= 50
3. 1 <= G,S <= 10000
4. 1 <= Aij,Bij <= 10000

Output

For each test case, output the case number first and then output the highest points in a line.

Sample Input

Sample Output

Case 1: 9
Case 2: 225

Author

hanshuai

Source

The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Final

看到这种棋盘问题求最大值那就是黑白染色最小割

把每个点拆成u v

白点 s 向 u 连一条权值为 w(当前点放金蛋) 的边 u 向 v连一条权值为INF 的边 v向t连一条权值为 w’(当前点放银蛋) 的边

黑点与之相反

然后黑点的u向相邻白点的v连一条权值为G的边

白点的u向黑点的u连一条权值为S的边

跑最小割即可

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d
", a)
#define plld(a) printf("%lld
", a)
#define pc(a) printf("%c
", a)
#define ps(a) printf("%s
", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 1e5 + 10, INF = 0x7fffffff;
int dir[4][2] = {{1, 0},{-1, 0},{0, 1},{0, -1}};

int n, m, G, S, s, t;

int head[maxn], cur[maxn], d[maxn], vis[maxn], nex[maxn << 1], cnt;

struct node
{
    int u, v, c;
}Node[maxn << 1];

void add_(int u, int v, int c)
{
    Node[cnt].u = u;
    Node[cnt].v = v;
    Node[cnt].c = c;
    nex[cnt] = head[u];
    head[u] = cnt++;
}

void add(int u, int v, int c)
{
    add_(u, v, c);
    add_(v, u, 0);
}

bool bfs()
{
    mem(d, 0);
    queue<int> Q;
    d[s] = 1;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = head[u]; i != -1; i = nex[i])
        {
            int v = Node[i].v;
            if(!d[v] && Node[i].c > 0)
            {
                d[v] = d[u] + 1;
                Q.push(v);
                if(v == t) return 1;
            }
        }
    }
    return d[t] != 0;
}

int dfs(int u, int cap)
{
    int ret = 0;
    if(u == t || cap == 0)
        return cap;
    for(int &i = cur[u]; i != -1; i = nex[i])
    {
        int v = Node[i].v;
        if(d[v] == d[u] + 1 && Node[i].c > 0)
        {
            int V = dfs(v, min(cap, Node[i].c));
            Node[i].c -= V;
            Node[i ^ 1].c += V;
            ret += V;
            cap -= V;
            if(cap == 0) break;
        }
    }
    if(cap > 0) d[u] = -1;
    return ret;
}

int Dinic()
{
    int ans = 0;
    while(bfs())
    {
        memcpy(cur, head, sizeof(head));
        ans += dfs(s, INF);
    }
    return ans;
}

int main()
{
    int T, kase = 0;
    rd(T);
    while(T--)
    {
        mem(head, -1);
        cnt = 0;
        int w;
        rd(n), rd(m), rd(G), rd(S);
        s = 0, t = n * m * 2 + 10;
        int sum = 0;
        rap(i, 1, n)
        {
            rap(j, 1, m)
            {
                rep(k, 0, 4)
                {
                    int nx = i + dir[k][0];
                    int ny = j + dir[k][1];
                    if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
                    add((i - 1) * m + j, n * m + (nx - 1) * m + ny, (((i + j) & 1) ? G : S));
                }
                rd(w);
                sum += w;
                if((i + j) & 1) add(s, (i - 1) * m + j, w);
                else add(n * m + (i - 1) * m + j, t, w);
                add((i - 1) * m + j, n * m + (i - 1) * m + j, INF);
            }
        }
        rap(i, 1, n)
            rap(j, 1, m)
            {
                rd(w);
                sum += w;
                if((i + j) & 1) add(n * m + (i - 1) * m + j, t, w);
                else add(s, (i - 1) * m + j, w);
            }
        printf("Case %d: ", ++kase);
        cout << sum - Dinic() << endl;


    }


    return 0;
}