【BZOJ-4213】贪吃蛇有上下界的费用流

4213: 贪吃蛇

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 58 Solved: 24
[Submit][Status][Discuss]

Description

最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。

在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。

新的游戏是这样的：

一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接)，且只是占据两个格子。蛇与蛇之间不能重叠，蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个：

1、两个端点所在的格子在网格的边界。

2、蛇构成一个环，即两个端点相邻(垂直或水平，不能斜着)，至少要占据4个格子(否则没法形成环)。

给定一个网格，用r x c的字符矩阵描述：‘#’代表障碍物，‘.’代表空地。在满足前面所述的条件下覆盖所有空地，并使得端点在网格边界(即不构成环)的蛇尽量少。（如果一条蛇既构成环，又是端点在边界，那么不计入答案）

例如，以下网格：

可以由下面三种方案覆盖。还有其他的方案，但是没法仅用一条不构成环的蛇就覆盖整个网络的方案。

给定一个网络的描述，输出最少需要多少条不构成环的蛇来覆盖这个网格。如果不存在能够覆盖网格的方案，输出-1。

Input

一个字符矩阵，行数和列数不超过12。输入文件中没有多余的空白字符，每行之后都有换行符。

Output

输出满足题目要求的那个整数。

Sample Input

......
.#.##.
.#....
....#.
.##.#.
......

Sample Output

HINT

Source

Solution

感觉是插头DP或者费用流...立马把插头DP否了

网格基本上得先黑白染色

感觉环状蛇中每个点一定与两个点相连，非环蛇只有头尾不合两个点相连，所以实际上要算的就是和一个点相连的

S-->白点，容量2 ：上下界都是2 费用为0

黑点-->T，容量2：上下界都是2 费用同样为0

表示这个点需要和别的两个点相连

然后白点向四周黑点扩展出一条边容量为1 费用为0

这样就是环状蛇的建图（显然环蛇不计入答案，所以费用全部置成0）

然后特判边界情况，边界上的白点-->T 费用1 容量1 表示非环蛇的情况

然后跑上下界最小费用流，ans/2即为答案，因为非环蛇的头尾都被累计，相当于1条蛇贡献2，所以除二即可

上下界最小费用流？理论什么的忘记了。。。

实现起来就是用超级源汇替代原来的源汇，再由次级汇连次级源INF，然后跑超级源汇之间的费用流

无解按照特有判定，S出来的边应该全都满流，否则无解

Code

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline 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 100010
#define MAXN 10010
int N,M,cas;
#define mN 15
#define mM 15
char G[mN][mM];
struct EdgeNode{int next,to,cap,cost;}edge[MAXM];
int head[MAXN],cnt=1;
inline void AddEdge(int u,int v,int w,int c) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w; edge[cnt].cost=c;}
inline void InsertEdge(int u,int v,int w,int c) {AddEdge(u,v,w,c); AddEdge(v,u,0,-c);}
int dis[MAXN],S,T,s,t,MinCost; bool mark[MAXN];
#define INF 0x7fffffff
bool spfa()
{
    queue<int>q; memset(mark,0,sizeof(mark));
    for (int i=S; i<=T; i++) dis[i]=INF;
    q.push(T); dis[T]=0; mark[T]=1;
    while (!q.empty())
        {
            int now=q.front(); q.pop(); mark[now]=0;
            for (int i=head[now]; i; i=edge[i].next)
                if (edge[i^1].cap && dis[edge[i].to]>dis[now]+edge[i^1].cost)
                    {
                        dis[edge[i].to]=dis[now]+edge[i^1].cost;
                        if (!mark[edge[i].to])
                            q.push(edge[i].to),mark[edge[i].to]=1;
                    }
        }
    return dis[S]!=INF;
}
int dfs(int loc,int low)
{
    mark[loc]=1;
    if (loc==T) return low;
    int w,used=0;
    for (int i=head[loc]; i; i=edge[i].next)
        if (edge[i].cap && !mark[edge[i].to] && dis[edge[i].to]==dis[loc]-edge[i].cost)
            {
                w=dfs(edge[i].to,min(low-used,edge[i].cap));
                edge[i].cap-=w; edge[i^1].cap+=w; used+=w; MinCost+=w*edge[i].cost;
                if (used==low) return low;
            }
    return used;
}
int zkw()
{
    int tmp=0;
    while (spfa())
        {
            mark[T]=1;
            while (mark[T])
                memset(mark,0,sizeof(mark)),tmp+=dfs(S,INF);
        }
    return tmp;
}
bool Judge() {bool f=1; for (int i=head[S]; i; i=edge[i].next) if (edge[i].cap) {f=0;break;} return !f;}
inline bool Check(int x,int y) {if (x>=1 && x<=N && y>=1 && y<=M && G[x][y]!='#') return 1; return 0;}
int D[mN*mM],id[mN][mM],col[mN][mM];
void BuildGraph()
{
    S=0; T=N*M+3; s=N*M+1; t=N*M+2; int idd=0;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            id[i][j]=++idd,col[i][j]=(i+j)&1;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            if (col[i][j])
                if (Check(i,j)) D[s]-=2,D[id[i][j]]+=2; else;
            else 
                if (Check(i,j)) D[id[i][j]]-=2,D[t]+=2; else;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            if (col[i][j] && Check(i,j))
                {
                    if (Check(i-1,j)) InsertEdge(id[i][j],id[i-1][j],1,0);
                    if (Check(i,j-1)) InsertEdge(id[i][j],id[i][j-1],1,0);
                    if (Check(i+1,j)) InsertEdge(id[i][j],id[i+1][j],1,0);
                    if (Check(i,j+1)) InsertEdge(id[i][j],id[i][j+1],1,0);
                }
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            if (i==1 || i==N || j==1 || j==M)
                if (col[i][j])
                    if (Check(i,j)) InsertEdge(id[i][j],t,1,1); else;
                else
                    if (Check(i,j)) InsertEdge(s,id[i][j],1,1); else;
    for (int i=1; i<=t; i++) 
        if (D[i]>0) InsertEdge(S,i,D[i],0);
            else 
        if (D[i]<0) InsertEdge(i,T,-D[i],0);
    InsertEdge(t,s,INF,0);
}
int tp;
int main()
{
    tp=1; while (scanf("%s",G[tp]+1)!=EOF) tp++;
    N=tp-1,M=strlen(G[1]+1);
    BuildGraph();
    zkw();
    if (Judge()) {puts("-1"); return 0;}
    printf("%d
",MinCost>>1);
    return 0;
}

什么垃圾读入方式，恶心！