HDU 4859 海岸线（最小割）

HDU 4859

海岸线

题目链接：here

海岸线

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 44 Accepted Submission(s): 7

Problem Description

欢迎来到珠海！ 由于土地资源越来越紧张，使得许多海滨城市都只能依靠填海来扩展市区以求发展。作为Z市的决策人，在仔细观察了Z市地图之后，你准备通过填充某些海域来扩展Z市的海岸线到最长，来吸引更多的游客前来旅游度假。为了简化问题，假设地图为一个N*M的格子，其中一些是陆地，一些是可以填充的浅海域，一些是不可填充的深海域。这里定义海岸线的长度为一个联通块陆地（可能包含浅海域填充变为的陆地）的边缘长度，两个格子至少有一个公共边，则视为联通。 值得注意的是，这里Z市的陆地区域可以是不联通的，并且整个地图都处在海洋之中，也就是说，Z市是由一些孤岛组成的，比如像，夏威夷？ 你的任务是，填充某些浅海域，使得所有岛屿的海岸线之和最长。

Input

输入第一行为T，表示有T组测试数据。 每组数据以两个整数N和M开始，表示地图的规模。接下来的N行，每一行包含一个长度为M的字符串，表示地图，‘.’表示陆地，’E’表示浅海域，’D’表示深海域。 [Technical Specification] 1. 1 <= T <= 100 2. 1 <= N, M <= 47

Output

对每组数据，先输出为第几组数据，然后输出最长的海岸线长度。

Sample Input

3
2 2
EE
EE
3 3
EEE
.E.
EEE
3 3
EEE
DED
EEE

Sample Output

Case 1: 8
Case 2: 16
Case 3: 20
Hint

对于第三组样例，一种可行方案是：

.E.
D.D
.E.

这样5个孤立小岛的海岸线总长为4 * 5 = 20。

Author

Isea@WHU

题目是中文的，题意不再赘述。直接搞。

.是陆地，D是海，E的话可以变成.或者D. 要求.的连通块组成的周长最长，其实就是相邻两个格子.E不同的个数要最多。

因为E有两个选择D或者. 其实就暗含了最小割的模型。 最小割的话，就是一部分分到源点一侧，一部分分到汇点一侧。 如果把源点分在一起当成是. 和汇点分在一起当成是D. 那么建图的时候，相邻的建流量为1的边。 如果这个点本来是. 那个连汇点是INF，本来是D的，连源点是INF。 如果是这种建图的话，最小割求出来的最小周长。 我们需要的最大周长。 稍微转化下。 我们希望相邻格子不同的最多，其实就是要相邻格子相同的最少。 所以用最小割来求相邻格子相同的最小值，然后总相邻数减掉这个就是答案了。 建图方法就是一开始进行奇偶染色。相当于对于点(x,y) 如果(x+y)%2 == 0 那么当成这个格子是 . 的，和源点分在一起。 如果(x+y)%2 == 1 那么当成这个格子是 D 的，和汇点分在一起。 相邻两点都建边。 这样建图的话，如果在源点一侧的跑到了汇点一侧，那么就相当于这个点从.变到D, 自然相同的数量要减少了、 汇点一侧的跑到了源点一侧，那么就相当于这个点从D变成了. 建图的时候，如果(x+y)%2==0 && 这个点本来就是D 或者 (x+y)%2 == 1 && 这个点本来就是. 那么这个点必须和汇点在一起，就把这个点和源点连INF的边。 相反情况类似处理。 这样建图出来的最小割，一定就是相邻格子是同一类的最小数量。总相邻减掉这个值就是答案了。 具体参见code

/* ***************

Author        :kuangbin

Created Time  :2014/7/21 11:52:20

File Name     :E:\2014ACM\HDU\HDU4859.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 10010;

const int MAXM = 100010;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow;

}edge[MAXM];

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];

void init()

{

    tol = 0;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w,int rw = 0)

{

    edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];

    edge[tol].flow = 0; head[u] = tol++;

    edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];

    edge[tol].flow = 0;head[v] = tol++;

}

int sap(int start,int end,int N)

{

    memset(gap,0,sizeof(gap));

    memset(dep,0,sizeof(dep));

    memcpy(cur,head,sizeof(head));

    int u = start;

    pre[u] = -1;

    gap[0] = N;

    int ans = 0;

    while(dep[start] < N)

    {

        if(u == end)

        {

            int Min = INF;

            for(int i = pre[u];i != -1;i = pre[edge[i^1].to])

                if(Min > edge[i].cap - edge[i].flow)

                    Min = edge[i].cap - edge[i].flow;

            for(int i = pre[u];i != -1;i = pre[edge[i^1].to])

            {

                edge[i].flow += Min;

                edge[i^1].flow -= Min;

            }

            u = start;

            ans += Min;

            continue;

        }

        bool flag = false;

        int v;

        for(int i = cur[u];i != -1;i = edge[i].next)

        {

            v = edge[i].to;

            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])

            {

                flag = true;

                cur[u] = pre[v] = i;

                break;

            }

        }

        if(flag)

        {

            u = v;

            continue;

        }

        int Min = N;

        for(int i = head[u];i != -1;i = edge[i].next)

            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)

            {

                Min = dep[edge[i].to];

                cur[u] = i;

            }

        gap[dep[u]]--;

        if(!gap[dep[u]])return ans;

        dep[u] = Min+1;

        gap[dep[u]]++;

        if(u != start)u = edge[pre[u]^1].to;

    }

    return ans;

}

char g[100][100];

int id[100][100];

int Move[][2] = { {0,1},{0,-1},{1,0},{-1,0}};

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

    int n,m;

    scanf("%d",&T);

    int iCase = 0;

    while(T--)

    {

        iCase++;

        scanf("%d%d",&n,&m);

        for(int i = 1;i <= n;i++)

            scanf("%s",g[i]+1);

        for(int i = 0;i <= m+1;i++)

        {

            g[0][i] = 'D';

            g[n+1][i] = 'D';

        }

        for(int i = 1;i <= n;i++)

        {

            g[i][0] = 'D';

            g[i][m+1] = 'D';

        }

        int cnt = 0;

        for(int i= 0;i <= n+1;i++)

            for(int j = 0;j <= m+1;j++)

                id[i][j] = ++cnt;

        init();

        int start = 0, end = cnt+1;

        int ans = 0;

        for(int i = 0;i <= n+1;i++)

            for(int j = 0;j <= m+1;j++)

            {

                for(int k = 0;k < 4;k++)

                {

                    int x = i + Move[k][0];

                    int y = j + Move[k][1];

                    if(x < 0 || x > n+1 || y < 0 || y > m+1)continue;

                    ans++;

                    addedge(id[i][j],id[x][y],1);

                }

                if(g[i][j] != 'E')

                {

                    if( ((i+j)%2 == 1 && g[i][j] == '.') || ((i+j)%2 == 0 && g[i][j] == 'D') )

                        addedge(start,id[i][j],INF);

                    else addedge(id[i][j],end,INF);

                }

            }

        printf("Case %d: %d\n",iCase,ans/2-sap(start,end,cnt+2));

    }

    return 0;

}