bzoj1066[SCOI2007]蜥蜴题解

Description

Input

Output

Sample Input

Sample Output

这是我的第一道非模板的网络流题目，&＃20540;得纪念。

在HHD大神的怂恿下，我尝试地做了这道题。结果不管怎么画图，还是不能把图建起来。

最大的一个难点在于，我发现它的权&＃20540;在点上而非边上。（有点像我最近做的USACO training上的题目）

最后还是参考了HHD大牛的题解，即所谓的拆点法。

    对于每个石柱，我们把它拆成2个点，称为入点和出点，入点和出点连一条边，容量为高度，如果A石柱能跳到B石柱，就把出点A和入点B连一条边，容量为无限，这条边模拟的是跳的过程。如果该石柱能跳出去，就在该石柱出点和汇点T连一条边，容量无限。这条边模拟跳出去的过程。 如果该石柱有蜥蜴，在源点S和该石柱入点连一条边，容量为1.
这样的话，每个有蜥蜴的石柱上都有一只蜥蜴，如果该蜥蜴想从该石柱跳开，必定要先从该石柱入点跑到该石柱出点，这样会消耗1的容量，然后跳出去后，跳到另一石柱时，想再跳的话，又会消耗那个石柱的容量 ，直到跳到汇点T，贡献了1的流量。所以这幅图的最大流表示的就是能逃脱的蜥蜴数量，输出答案时减一下就行了。

为了加深理解，我尝试地画了一幅图。             
        以下是代码：

#include
#include
#include
const int INF=999999;
char c,u,a[21][21];
int map[1002][1002],fin[21][21],n,m,d,cnt,ant,ans,i,j,x[20001],pre[1001];
using namespace std;
void make_picture(int x,int y)
{
int now=fin[x][y]+1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if ((i!=x||j!=y)&&(a[i][j]>‘0‘))
{
if (d*d>=(x-i)*(x-i)+(y-j)*(y-j))
map[now][fin[i][j]]=INF;
}
}
void go_down()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (i-d<1||i+d>n||j-d<1||j+d>m)
{
int now=fin[i][j]+1;
map[now][cnt]=INF;
}
}
void flow()
{
while (true)
{
int h=0,t=1;x[1]=0;
memset(pre,-1,sizeof(pre));
while (h {
int now=x[++h];
for (int i=1;i<=cnt;i++)
if (pre[i]<0&&map[now][i]>0)
{
x[++t]=i;pre[i]=now;
}
if (pre[cnt]>0) break;
}
if (pre[cnt]<0) break;int small=INF;
for (i=cnt;i!=0;i=pre[i]) small=min(map[pre[i]][i],small);
for (i=cnt;i!=0;i=pre[i]) {map[pre[i]][i]-=small;map[i][pre[i]]+=small;}
ans+=small;
}
}
int main()
{
scanf("%ld%ld%ld",&n,&m,&d);
scanf("%c",&u);cnt=0;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
scanf("%c",&a[i][j]);
if (a[i][j]!=‘0‘)
{
cnt++;fin[i][j]=cnt;
map[cnt][cnt+1]=a[i][j]-48;cnt++;
}
}
scanf("%c",&u);
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
scanf("%c",&c);
if (c==‘L‘) {ant++;map[0][fin[i][j]]=1;}
if (a[i][j]>‘0‘) {make_picture(i,j);}
}
scanf("%c",&u);
}
cnt++;go_down();
flow();
printf("%ld",ant-ans);
return 0;
}

bzoj 1066 [SCOI2007] 蜥蜴 题解,布布扣,bubuko.com