本文正體字版由OpenCC轉換
做出這道題關鍵在於讀懂題目，尤其是第3條和第4條規則。可以知道，所有螞蟻是一擁而上的，而且螞蟻很聰明，它們知道如果在某時一隻螞蟻到瓢蟲的路 徑與另一隻螞蟻的路徑相互包含，就讓距離近的螞蟻繼續行進，另一隻螞蟻停留不動。螞蟻們還會互相禮讓，如果要同時進入一個節點，就讓編號小的螞蟻進入，其 它螞蟻停止不再動。
瓢蟲會停留在多個位置，但是都是互相不關聯的，我們可以把瓢蟲停留的每個位置看作獨立的測試點，每個測試點要用到上個測試點的結果，所以我們可以分割考慮每次瓢蟲停留。
對於每次瓢蟲停留，如果簡單地模擬，會很容易超時。我們要把每隻螞蟻一次移動到位。首先從瓢蟲的位置開始一遍BFS，找到所有可行進的螞 蟻，記錄每隻螞蟻到瓢蟲位置的路徑。然後按照路徑長度從小到大爲第一關鍵字，螞蟻編號從小到大爲第二關鍵字把螞蟻進行排序，排名第一的螞蟻一定是可以驅逐 瓢蟲的螞蟻，把它的路徑上的頂點分別標記時間。然後依次處理每隻螞蟻，如果某隻螞蟻路徑上有節點已經被標記時間，則這隻螞蟻的最大移動時間就是已經標記的 時間。在移動時也標記時間，用於影響後面的螞蟻。這樣，移動所有螞蟻的時間複雜度是O(N+K)的。
算法的總的時間複雜度爲O((N+K*logK)*L)，可以很快解決問題。實際編寫時有很多細節需要注意。
/*
* Problem: POI2001 mro
* Author: Guo Jiabao
* Time: 2009.2.2 21:43
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=5001,MAXK=1001,INF=0x7FFFFFFF;
struct edge{int t;edge *next;};
struct adjl{edge *f,*l;};
struct vertex{int id,ant,label;};
struct ant{int vtx,id,dist,hits;};
struct path{path *from;int p;};
edge E[MAXN*2];
adjl A[MAXN];
vertex V[MAXN];
ant Ant[MAXK];
int PL[MAXK],Pt[MAXK][MAXN];
int N,K,L,Ec=-1,Target;
int Order[MAXK];
inline void addedge(int a,int b)
{
if (A[a].f)
A[a].l=A[a].l->next=&E[++Ec];
else
A[a].f=A[a].l=&E[++Ec];
E[Ec].t=b;
}
void init()
{
int i,a,b;
freopen("mro.in","r",stdin);
freopen("mro.out","w",stdout);
scanf("%d",&N);
for (i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
for (i=1;i<=N;i++)
V[i].id=i;
scanf("%d",&K);
for (i=1;i<=K;i++)
{
scanf("%d",&a);
V[a].ant=i;
Ant[i].id=i;
Ant[i].vtx=a;
Order[i]=i;
}
scanf("%d",&L);
}
void BFS()
{
path Queue[MAXN],u,v;
int Head=0,Tail=0;
bool vis[MAXN];
int *P;
memset(vis,0,sizeof(vis));
Queue[0].p=Target;
Queue[0].from=0;
vis[Target]=true;
while (Head<=Tail)
{
v.from=&Queue[Head];
u=Queue[Head++];
for (edge *k=A[u.p].f;k;k=k->next)
{
v.p=k->t;
if (!vis[v.p])
{
vis[v.p]=true;
if (V[v.p].ant!=0)
{
int a=V[v.p].ant;
path *b=&v;
PL[a]=0;
P=Pt[a];
while (b->from)
{
P[++PL[a]]=b->p;
b=b->from;
}
P[++PL[a]]=Target;
Ant[a].dist=PL[a]-1;
}
else
Queue[++Tail]=v;
}
}
}
}
void Move()
{
int p,i,j,u,v,MaxStep,Step;
i=Order[1];
Ant[i].hits++;
MaxStep=PL[i];
for (p=1;p<=K && Ant[i=Order[p]].dist<INF;p++)
{
Step=MaxStep;
for (j=1;j<=PL[i];j++)
{
u=Pt[i][j];
if (V[u].label)
{
Step=V[u].label+1;
break;
}
}
u=Pt[i][1];
V[u].ant=0;
for (j=2;j<=Step;j++)
{
v=Pt[i][j];
if (V[u].label+1 > V[v].label)
V[v].label=V[u].label+1;
else
break;
u=v;
}
Ant[i].vtx=u;
V[u].ant=i;
}
}
inline int cmp(const void *a,const void *b)
{
int A=*(int *)a,B=*(int *)b;
if ( Ant[A].dist < Ant[B].dist ) return -1;
if ( Ant[A].dist > Ant[B].dist ) return 1;
if ( Ant[A].id < Ant[B].id ) return -1;
return 1;
}
void clear()
{
int i;
for (i=1;i<=K;i++)
Ant[i].dist=INF;
for (i=1;i<=N;i++)
V[i].label=0;
}
void solve()
{
int i,a;
for (i=1;i<=L;i++)
{
scanf("%d",&Target);
if (V[Target].ant!=0)
{
a=V[Target].ant;
Ant[a].hits++;
}
else
{
clear();
BFS();
qsort(Order+1,K,sizeof(Order[0]),cmp);
Move();
}
}
for (i=1;i<=K;i++)
{
printf("%d %dn",Ant[i].vtx,Ant[i].hits);
}
}
int main()
{
init();
solve();
return 0;
}
<h2><span class="mw-headline">螞蟻和瓢蟲 </span></h2>
螞蟻和蚜蟲是共生的。蚜蟲分泌出蜜汁給螞蟻引用。螞蟻幫助蚜蟲趕走它的天敵——瓢蟲。在螞蟻山附近有一個樹，這裏是蚜蟲生活的地方。蚜蟲吸取樹的汁 液。有n個螞蟻兵，用1到n編號。一個瓢蟲威脅着這個文明，它經常出現在蚜蟲活動的地方。當瓢蟲坐在樹上時，螞蟻兵會出動把它趕走。他們按照如下的規則：
樹上的任意兩點之間都只有一條路徑,所有的螞蟻都沿着它所在點到瓢蟲的路徑前進，每移動一個位置，花的時間是單位1。
-
如果螞蟻和瓢蟲在同一個位置，那麼螞蟻立即把它趕走。
-
如果某個螞蟻的路徑上有另外一隻螞蟻，那麼距離目標較遠的螞蟻待在原地不動，較近的那個螞蟻繼續前進。
-
如果有多個螞蟻要進入同一個位置，那麼選擇編號最小的螞蟻，其餘的螞蟻留在原位置不動。
-
當螞蟻到達了瓢蟲的位置以後，把它趕走，然後停留在該位置。
瓢蟲是非常頑固的動物，它被趕走了以後還會再停留到別的位置。然後螞蟻繼續行動。爲了使問題簡單化，我們假定從一個位置到達與它相鄰的位置花1個單位的時間。
任務：
讀入樹的描述，螞蟻的開始位置，以及瓢蟲停留地點。 給出每個螞蟻的最後的位置，以及該螞蟻趕走瓢蟲的次數。
輸入：
文件的第一行，一個整數n，1<=n<=5000。表示地點的編號。接下來n-1行描述了樹裏的邊，每行兩個整數a和b，表示 這兩點之間相連。然後一行是整數k，1<=k<=1000 and k<=n。是螞蟻兵的數目。接下來k行，每行一個整數，表示螞蟻兵開始的位置。沒有兩個螞蟻位於一個位置。然後是一個整數l, 1<=l<=500,即瓢蟲停留l次。下面的l行每行一個整數，表示瓢蟲依次停留的位置。
輸出：
k行。每行兩個整數，分別表示第k個螞蟻最後的位置以及它趕走瓢蟲的次數。
Sample Input
4 1 2 1 3 2 4 2 1 2 2 2 4
Sample Output
1 0 4 2
Figure
上次修改時間 2017-05-22