题解 P2445 【[SDOI2005]动物园】
不得不说洛谷的管理效率实在是高，一天就把spj加上了，先赞一个。
这道题目大意是给出动物的速度和某个时刻的位置，把动物和笼子配对。
首先可以看出所给出的某个时刻某动物在何处的信息中有一些是多余的。对于每个动物来说，只需要保留它被看到的时间最早的信息即可，因为如果我们知道某动物在T1时刻在(x1,y1),在T2时刻在(x2,y2)(T1<T2),且这两个信息都合法，那么我们只要知道了第一条信息，我们可以推出在T2时刻动物可能在(x2,y2)。
对于每个动物所保留下来的信息进行一次搜索，确定这个动物可能是从哪个笼子里出来的，具体方式是从这个点开始往外进行floodfill，如果到达笼子的格子数<=动物的速度*时间，就认为这个动物可能是从这个笼子里出来的。
如果一个动物没有被观测到，那么认为它有可能是从任何一个笼子里出来的。
然后就变成了每个动物有一个对应的笼子集合，然后进行一次最大匹配。
最大匹配的算法可以采用最大流或者匈牙利算法。
题目保证有解，所以在匹配完成后输出对应方案即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct st{
int t,x,y;
}animal[205];
const int inf=1e9+7;
#define min(a,b) (a<b?a:b)
int maps[10001],cage[10001],p,n,qu,ways[10001],v[205];
char ch[102];
int num[10001],exist[205],nums,cagenum[1001];
int head[505],nxt[80005],point[80005],remain[80005],sum;
int nowedge[505],deep[505];
int a,b,c,d;
queue<int>q;
void dfsmap(int x,int y,int d)
{
if(x>n||x<1||y>n||y<1) return;
if(maps[x*n-n+y]==-1) return;
if(ways[x*n-n+y]<=d) return;
ways[x*n-n+y]=d;
dfsmap(x+1,y,d+1);
dfsmap(x-1,y,d+1);
dfsmap(x,y+1,d+1);
dfsmap(x,y-1,d+1);
}
void divide()
{
sum=-1;
memset(head,-1,sizeof(head));
memset(nxt,-1,sizeof(nxt));
nums=p;
for(int i=1;i<=n*n;i++)
if(cage[i])
num[i]=++nums,cagenum[nums]=i;
}
void add(int x,int y,int flow)
{
++sum;nxt[sum]=head[x];head[x]=sum;point[sum]=y;remain[sum]=flow;
++sum;nxt[sum]=head[y];head[y]=sum;point[sum]=x;remain[sum]=0;
}
void addall(int ani)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int now=i*n-n+j;
if(cage[now]) add(ani,num[now],1);
}
}
void search(int times,int x,int y,int ani)
{
memset(ways,127,sizeof(ways));
dfsmap(x,y,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int now=i*n-n+j;
if(cage[now]&&ways[now]<times)
add(ani,num[now],1);
}
}
void setup()
{
for(int i=1;i<=p;i++)
add(0,i,1);
for(int i=p+1;i<=nums;i++)
add(i,nums+1,cage[cagenum[i]]);
}
bool bfs(int s,int t)
{
for(int i=0;i<=nums;i++)
nowedge[i]=head[i];
memset(deep,127,sizeof(deep));
deep[s]=0;
q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
for(int tmp=head[now];tmp!=-1;tmp=nxt[tmp])
{
int u=point[tmp];
if(remain[tmp]&&deep[u]>inf)
{
deep[u]=deep[now]+1;
q.push(u);
}
}
}
return deep[t]<inf;
}
int dfs(int x,int t,int limit)
{
if(x==t||!limit) return limit;
int flow=0,f;
for(int tmp=nowedge[x];tmp!=-1;tmp=nxt[tmp])
{
nowedge[x]=tmp;
if((deep[point[tmp]]==deep[x]+1)&&(f=dfs(point[tmp],t,min(limit,remain[tmp]))))
{
flow+=f;
limit-=f;
remain[tmp]-=f;
remain[tmp^1]+=f;
}
}
return flow;
}
void dinic(int s,int t)
{
while(bfs(s,t))
dfs(s,t,inf);
}
void getans()
{
dinic(0,nums+1);
for(int i=1;i<=p;i++)
{
printf("%d ",i);
for(int tmp=head[i];tmp!=-1;tmp=nxt[tmp])
{
if(point[tmp]&&(remain[tmp]==0))
{
int now=cagenum[point[tmp]],nowx,nowy;
nowx=now/n;
if(now%n==0) nowy=n;
else nowx++,nowy=now%n;
printf("%d %d\n",nowx,nowy);
break;
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
for(int j=0;j<n;j++)
if(ch[j]=='*') maps[i*n-n+j+1]=-1;
}
scanf("%d",&p);
for(int i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
cage[a*n-n+b]++;
}
divide();
for(int i=1;i<=p;i++)
scanf("%d",&v[i]);
memset(animal,127,sizeof(animal));
scanf("%d",&qu);
for(int i=1;i<=qu;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a>=animal[d].t) continue;
animal[d]=(st){a,b,c};
exist[d]=1;
}
for(int i=1;i<=p;i++)
if(exist[i])
search(animal[i].t*v[i],animal[i].x,animal[i].y,i);
else
addall(i);
setup();
getans();
}