【GCJ2008E】日程表最小割

Google Code Jam 2008 E 日程表

【题目描述】

热情的选手Sphinny正在看新一年的日程表，并发现已经安排了很多编程竞赛。她将这一年的每一天都用以下三种方式之一在日程表上打标记。

1.白色：这一天她将不参加竞赛。或许这一天没有预定的竞赛，或许这一天有更重要的事情要做（生活中肯定还有其他美好的事情）。

2.蓝色：这一天她将参加一场竞赛。

3.问号：这一天有预定好的竞赛，但她还没有决定好是否参加。

为了简化问题，我们假设没有资格的概念：你不必参加一场比赛去取得另一场比赛的参赛资格。

Sphinny生活的世界与我们的世界有所不同，那个世界里一年有n个月，每个月恰有m天。

下面的图片是一张5个月，每个月有8天的日程表。上面有15天标记为蓝色，5天标记了问号。

看她美丽的日程表。Sphinny认为对于每一天，有四天与它相邻（可能有的不存在）：同一个月的前一天，同一个月的后一天，前一个月的同一天，后一个月的同一天。

Sphinny想最大化所有竞赛的喜悦值之和。一场竞赛的喜悦值的计算方式是：

1.初始为4。

2.每有与那一天相邻的一天要参赛，喜悦值减1。（你可以认为Sphinny喜欢竞赛，但连续参赛让她感觉很累。并且出于审美的原因，在相邻两个月的同一天参赛也不是很好。）

现在，Sphinny想计划这一年，并决定把每一个问号标记都改为白色标记或蓝色标记。她的目标很简单，就是最大化总喜悦值。

下图是上面例子的一种解决方案。通过把2个问号标记变为蓝色标记，剩下的3个问号标记变为白色标记，她可以得到喜悦值42。

【输入格式】

第一行一个整数T表示测试数据组数。

对于每一组数据：第一行两个整数n，m表示有n个月，每个月有m天。之后n行每行一个长度为m的字符串，第i行第j个字符表示第i个月的第j 天的状态，“#”表示这一天被标记为蓝色，“.”表示这一天被标记为白色，"?”表示这一天被标记为问号。

【输出格式】

对于每一组数据，输出： Case #X: Y

X是第几组测试数据，Y是最大总喜悦值。

【输入样例】

3 3

.?.

.#.

5 8

.#...##.

.##..?..

.###.#

.# ??#.

.?.. ##

#?#...

【输出样例】

Case #1: 8

Case #2: 42

【数据范围】

对于30%的数据，1≤n,m≤5

对于60%的数据，1≤n,m≤15

对于100%的数据，1≤n,m≤50，1≤T≤100

Solution

评测链接评测数据

30%乱搞暴力 60%可以状压DP 100%最小割

要求总收益最大，可以转化为 损失最小 ，然后答案就是可以获得的最大总收益-最小损失可以利用最小割来求解

考虑对方格进行黑白染色

“.”点对答案没有影响，所以不用考虑，考虑“#”“?”的相互影响即可

那么我们先预处理出$tot=sum val[i] + sum sc[i] $ 其中 $val[i]$表示“?”点的预期得分（4-2*四联通的“#”数），$sc[i]$表示已经确定的“#”的确定得分

那么考虑最小割建模

S连白色“?”点，容量为 $val[i]$

黑色“?”点连T，容量为 $val[i]$

相邻的黑白点，由白“?”点向黑“?”点，容量为$2$

考虑一个割，如果割的是与S相连的边，表示这个白点不变蓝，如果割与T相连，表示这个黑点不变蓝，如果割中间边，表示都变蓝

这里有个值得注意的地方，对于一个“?”点，如果他的四联通中有$>=2$个“#”点，那么这个点我们可以忽略

最后答案为$Ans=tot-mincut$

faebdc学长的标解：

初始化ans为所有问号标记都为白色标记时的喜悦值，再将ans加上问号标记个数的4倍。那么：
1. 问号标记变为白色标记，ans要减4。
2.问号标记变为蓝色标记，若它周围有tot个一开始就是蓝色的标记，ans要减去2*tot。
3. 两个相邻的问号标记?_1和?_2都变为蓝色标记，ans要减去2。
建图时，让每一个问号标记对应着图中的一个点。考虑前两种情况，可以让每个点与源点、汇点各连一条边，流量为4和2*tot。考虑第三种情况，?_1和?_2都变为蓝色标记时，ans要减去2，可以使用下图这样的建图方式。
这样，只有相邻两个问号标记都变为蓝色标记时，连接这两个问号标记的边才会被割掉，使ans减小2。
将网格染色，相邻的格子颜色不同，就会形成二分图。一种颜色的点用?_1的连接方式，另一种颜色的点用?_2的连接方式。
ans减去求出的最大流即为答案。

标准建图

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
void Freopen() {freopen("cal.in","r",stdin); freopen("cal.out","w",stdout);}
void Fclose() {fclose(stdin); fclose(stdout);}
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define MAXM 1000100
#define MAXN 100100
int N,M,cas,Cas;
char G[100][100];
struct EdgeNode{int next,to,cap;}edge[MAXM];
int head[MAXN],cnt=1;
void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w;}
void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,0);}
int dis[MAXN],que[MAXN<<1],cur[MAXN],S,T;
bool bfs()
{
    for (int i=S; i<=T; i++) dis[i]=-1;
    que[0]=S; dis[S]=0; int he=0,ta=1;
    while (he<ta)
        {
            int now=que[he++];
            for (int i=head[now]; i; i=edge[i].next)
                if (edge[i].cap && dis[edge[i].to]==-1)
                    dis[edge[i].to]=dis[now]+1,que[ta++]=edge[i].to;
        }
    return dis[T]!=-1;
}
int dfs(int loc,int low)
{
    if (loc==T) return low;
    int w,used=0;
    for (int i=cur[loc]; i; i=edge[i].next)
        if (edge[i].cap && dis[edge[i].to]==dis[loc]+1)
            {
                w=dfs(edge[i].to,min(low-used,edge[i].cap));
                edge[i].cap-=w; edge[i^1].cap+=w;
                used+=w; if (edge[i].cap) cur[loc]=i;
                if (used==low) return low;
            }
    if (!used) dis[loc]=-1;
    return used;
}
#define inf 0x7fffffff
int dinic()
{
    int tmp=0;
    while (bfs())
        {
            for (int i=S; i<=T; i++) cur[i]=head[i];
            tmp+=dfs(S,inf);
        }
    return tmp;
}
bool OK(int x,int y) {return (x>=1 && x<=N)&&(y>=1 && y<=M);}
int Get(int x,int y)
{
    int re=0;
    if (OK(x-1,y) && G[x-1][y]=='#') re++;
    if (OK(x+1,y) && G[x+1][y]=='#') re++;
    if (OK(x,y-1) && G[x][y-1]=='#') re++;
    if (OK(x,y+1) && G[x][y+1]=='#') re++;
    return re; 
}
int id[100][100],ID,col[100][100];
void init() {cnt=1; memset(head,0,sizeof(head)); ID=0;}
void BuildGraph()
{
    int Tot=0;
    init();
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            id[i][j]=++ID,col[i][j]=(i+j)&1;
    S=0; T=ID+1;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            {
                if (G[i][j]=='#') Tot+=4-Get(i,j);
                if (G[i][j]=='?') if (Get(i,j)<2)  Tot+=4-2*Get(i,j);
            }
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            if (G[i][j]=='?')
                if (col[i][j])
                    {
                        if (Get(i,j)<2) 
                            {
                                InsertEdge(S,id[i][j],4-2*Get(i,j));
                                if (OK(i-1,j) && G[i-1][j]=='?') InsertEdge(id[i][j],id[i-1][j],2);
                                if (OK(i+1,j) && G[i+1][j]=='?') InsertEdge(id[i][j],id[i+1][j],2);
                                if (OK(i,j-1) && G[i][j-1]=='?') InsertEdge(id[i][j],id[i][j-1],2);
                                if (OK(i,j+1) && G[i][j+1]=='?') InsertEdge(id[i][j],id[i][j+1],2);
                            }
                    }
                else 
                    if (Get(i,j)<2) InsertEdge(id[i][j],T,4-2*Get(i,j));
    int MaxFlow=dinic();
    printf("Case #%d: %d
",Cas-cas,Tot-MaxFlow);
}
int main()
{
    Freopen();
    Cas=cas=read();
    while (cas--)
        {
            N=read(),M=read();
            for (int i=1; i<=N; i++)
                for (int j=1; j<=M; j++)
                    cin>>G[i][j];
            BuildGraph();
        }
    Fclose();
    return 0;
}