NKOJ 2284 （BZOJ 4213）贪吃蛇 （上下界网络流）

发表于 |
字数统计: 1,129字 | 阅读时长 ≈ 6min

P2284【L1 SOLO 第九场 HN11 day1】贪吃蛇

问题描述

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

  1. 两个端点所在的格子在网格的边界。
  2. 蛇构成一个环，即两个端点相邻（垂直或水平，不能斜着），至少要占据4个格子（否则没法形成环）。
    给定一个网格，用r * c的字符矩阵描述：’#’代表障碍物，’.’代表空地。在满足前面所述的条件下覆盖所有空地，并使得端点在网格边界（即不构成环）的蛇尽量少。
    例如，以下网格：
    ……
    .#.##.
    .#….
    ….#.
    .##.#.
    ……
    可以由下面三种方案覆盖。还有其它的方案，但是没有仅用一条不构成环的蛇就覆盖整个网格的方案。
    这里写图片描述
    给定一个网格的描述，输出最少需要多少条不构成环的蛇来覆盖这个网格。如果不存在能够覆盖网格的方案，输出-1。

输入格式

的空白字符，每行之后都有换行符。

输出格式

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

样例输入

……
.#.##.
.#….
….#.
.##.#.
……

样例输出

2

一道很玄的题目。

首先染色，染成黑白两色，
然后从源点连到白色格子连一条上界为2，下界也为2的边
然后从黑色格子连到汇点连一条上界为2，下界也为2的边
然后从白色格子往相邻的格子连一条容量为1的边
然后从源点连到边界上的黑色格子，连一条容量为1，费用为1的边
然后从边界上的白色格子连到汇点，连一条容量为1，费用为1的边
求上图的最小费用最大流即可。答案就是费用/2

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 300
#define M 5000
using namespace std;
int n,m,S,T,P,s,t,id[N][N],D[N],lim;
char map[N][N];
int TOT=1,LA[N],NE[M],EN[M],G[M],LE[M];
int slk[N],dis[N],maxflow,mincost;
bool mark[N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void ADD(int x,int y,int z,int c)
{
	TOT++;
	EN[TOT]=y;
	G[TOT]=z;
	LE[TOT]=c;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int FP(int x,int f)
{
	int i,y,tmp,t,d=0;
	if(x==T)return maxflow+=f,mincost+=f*dis[S],f;
	mark[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(!G[i]||mark[y])continue;
		t=dis[y]+LE[i]-dis[x];
		if(!t)
		{
			tmp=FP(y,min(f-d,G[i]));
			d+=tmp;G[i]-=tmp;G[i^1]+=tmp;
			if(f==d)return f;
		}
		else slk[y]=min(slk[y],t);
	}
	return d;
}
bool AF()
{
	int i,d=1e9;
	for(i=1;i<=T;i++)if(!mark[i])d=min(d,slk[i]),slk[i]=1e9;
	if(d==1e9)return 0;
	for(i=1;i<=T;i++)if(mark[i])dis[i]+=d;
	return 1;
}
int main()
{
	int i,j,k,x,y,u,d;
	while(scanf("%s",&map[++n][1])!=EOF)map[n][0]='%';
	n--;m=strlen(map[n])-1;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)if(map[i][j]=='.')id[i][j]=++P;
	s=P+1;t=s+1;S=t+1;T=S+1;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	if((i+j&1)&&id[i][j])
	{
		D[s]-=2;D[id[i][j]]+=2;
		if(i==1||i==n||j==1||j==m)ADD(id[i][j],t,1,1),ADD(t,id[i][j],0,-1);
	}
	else if((!(i+j&1))&&id[i][j])
	{
		D[id[i][j]]-=2,D[t]+=2;
		if(i==1||i==n||j==1||j==m)ADD(s,id[i][j],1,1),ADD(id[i][j],s,0,-1);
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(k=0;(i+j&1)&&id[i][j]&&k<4;k++)
	{
		x=i+dx[k];y=j+dy[k];
		if(id[x][y])ADD(id[i][j],id[x][y],1,0),ADD(id[x][y],id[i][j],0,0);
	}
	for(i=1;i<=t;i++)
	if(D[i]>0)ADD(S,i,D[i],0),ADD(i,S,0,0),lim+=D[i];
	else if(D[i]<0)ADD(i,T,-D[i],0),ADD(T,i,0,0);
	ADD(t,s,1e9,0);ADD(s,t,0,0);
	memset(slk,60,sizeof(slk));
	do{
		do{
			memset(mark,0,sizeof(mark));
		}while(FP(S,1e9));
	}while(AF());
	if(maxflow<lim)puts("-1");
	else printf("%d",mincost/2);
}