bzoj 1066:[SCOI 2007]トカゲ(最大流)

1066:[SCOI 2007]トカゲ
Time Limit: 1 Sec  
Memory Limit: 162 MB
Submit: 4116  
Solved: 2081
[ Submit][ Status][ Discuss]
Description
r行c列のグリッドマップには高さの異なる石柱があり、いくつかの石柱にはトカゲが立っています.あなたの任務はできるだけ多くのトカゲを境界の外に逃がすことです.各行の各列の隣接する石柱の距離は1であり、トカゲのジャンプ距離はdであり、すなわちトカゲは平面距離がdを超えないいずれかの石柱にジャンプすることができる.石柱は不安定で、トカゲがジャンプするたびに離れた石柱の高さが1(地図の内部に落ちている場合は到達した石柱の高さが変わらない)減少し、その石柱の元の高さが1であればトカゲは離れて消えてしまう.その後他のトカゲは足を踏み入れることができない.いつでも2匹のトカゲが同じ石柱にいることはできない.
Input
第1の挙動の3つの整数r,c,d,すなわち地図の規模と最大ジャンプ距離を入力する.以下rは石竹の初期状態を示し、0は石柱がないことを示し、1~3は石柱の初期高さを示す.以下rはトカゲの位置を表し、「L」はトカゲを表す.トカゲがいないことを示す.
Output
出力は1行のみで、脱出できないトカゲの総数の最小値を含む整数です.
Sample Input
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
Sample Output
1
ネットの流れを見ると、実はこのような変な状況が複雑だと感じますが、データが特に小さい問題は一般的にネットの流れです.
ポイントを分解するには:各柱を1つの入点と1つの出点に分解します.
①全ての源点がトカゲのある点(入点)に流れ1の辺をつなぐ
②飛び出すことができる全ての柱の出点が合流点につながっている流れが無限の辺
③互いに跳べる全ての柱は、一方の柱の出点が他方の柱の入点に向かって無限の流れを持つ辺に連なっている
(AはBまで、BはAまで)
④1つの柱の入点この柱の出点に長さが柱の高さの辺を接続する
答えはトカゲの数-最大流

#include
#include
#include
#include
#define LL long long 
#define inf 2147483647
using namespace std;
char str[25][25];
LL n, m, cnt, S, T, head[2005], h[2005], cur[2005];
typedef struct
{
	LL to, next;
	LL flow;
}Road;
Road G[20005];
void Add(LL u, LL v, LL flow)
{
	cnt++;
	G[cnt].next = head[u];
	head[u] = cnt;
	G[cnt].to = v;
	G[cnt].flow = flow;
}
int Jud()
{
	LL now, i;
	queue q;
	memset(h, -1, sizeof(h));
	q.push(S);
	h[S] = 0;
	while(q.empty()==0)
	{
		now = q.front();
		q.pop();
		for(i=head[now];i!=0;i=G[i].next)
		{
			if(G[i].flow && h[G[i].to]==-1)
			{
				h[G[i].to] = h[now]+1;
				q.push(G[i].to);
			}
		}
	}
	if(h[T]!=-1)
		return 1;
	return 0;
}
LL Sech(LL x, LL flow)			//     flow              
{
	LL w, used, i;
	if(x==T)
		return flow;
	used = 0;
	for(i=cur[x];i!=0;i=G[i].next)
	{
		if(h[G[i].to]==h[x]+1)
		{
			w = Sech(G[i].to, min(flow-used, G[i].flow));
			G[i].flow -= w;
			G[i^1].flow += w;
			if(G[i].flow)
				cur[x] = i;
			used += w;
			if(used==flow)		//            （        ），         
				return flow;
		}
	}
	if(used==0)				//                   ，          ，  
		h[x] = -1;
	return used;
}
LL Dinic()
{
	LL i, flow = 0;
	while(Jud())
	{
		for(i=S;i<=T;i++)
			cur[i] = head[i];
		flow += Sech(S, inf);
	}
	return flow;
}
int main(void)
{
	int n, m, i, j, k, f, d, sum;
	while(scanf("%d%d%d", &n, &m, &d)!=EOF)
	{
		cnt = 1;
		S = 0, T = 2*n*m+1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				scanf(" %c", &str[i][j]);
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(str[i][j]=='0')
					continue;
				if(i<=d || n-i=(k-i)*(k-i)+(f-j)*(f-j))
						{
							Add(m*(n+i-1)+j, m*(k-1)+f, inf);
							Add(m*(k-1)+f, m*(n+i-1)+j, 0);
						}
					}
				}
			}
		}
		sum = 0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf(" %c", &str[i][j]);
				if(str[i][j]!='.')
				{
					sum++;
					Add(S, m*(i-1)+j, 1);
					Add(m*(i-1)+j, S, 0);
				}
			}
		}
		printf("%d
", sum-Dinic());
	}
	return 0;
}