http://acm.fzu.edu.cn/problem.php?pid=2169

题目大意：

S王国有N个城市，有N-1条道路。王都为编号1的城市。叛军驻扎在很多城市。除了王都外有K个城市有军队，这K支军队要向王都进军，而且消灭沿途经过的城市中的叛军。每支军队仅仅能沿着道路走，而且是其所在城市与王都之间的最短路线走。问可以消灭多少叛军？

思路：

有两种方法。

注意到题目仅仅有N-1条边。是一颗树。

我想到的是对编号为1的结点（也就是王都，作为跟结点）进行DFS，一直遍历到树叶为止。沿途若发现有军队的，则往上传递可消灭叛军的信息。详见代码。

A了之后看了看别人的思路有方法二：

是对每一个有军队的城市进行SPFA。每次消灭一次叛军就把叛军消除（Num置为0） 直到没有叛军或者所有军队遍历完。

但我总认为怪怪的，军队向王都经过最短路径，可是方向不一定对啊！

如以下这组数据：

11 1

0 0 0 0 0 3 4 0 5 0 0

5 

1 2 

2 3

2 4

3 5

5 6

5 7

7 8

8 9

8 10

9 11

SPFA的结果为12.而DFS的为0.

按我对题目的理解也是0.

两个代码均AC。题目含糊。。

方法一：DFS

#include<cstdio>

#include<cstring>

const int MAXN=100000+10;

const int INF=0x3ffffff;

int head[MAXN],len,n,k,ans;

int num[MAXN];

bool vis[MAXN], army[MAXN];

struct edge

{

	int to,next;

}e[MAXN<<1];

void add(int from,int to)

{

	e[len].to=to;

	e[len].next=head[from];

	head[from]=len++;

}

bool dfs(int cur)

{

	for(int i=head[cur];i!=-1;i=e[i].next)

	{

		int id=e[i].to;

		if(vis[id])

			continue;

		vis[id]=true;

		if(dfs(id))

		{

			if(num[id]!=0)

				ans+=num[id];

			return true;

		}

		if(army[id] ==true)  //有军队

			return true;

	}

	return false;

}

int main()

{

	while(~scanf("%d%d",&n,&k))

	{

		int cnt=0;

		memset(head,-1,sizeof(head));

		memset(vis,0,sizeof(vis));

		len=0;

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&num[i]);

			if(num[i])

				cnt++;

		}

		for(int i=0;i<k;i++)

		{

			int temp;

			scanf("%d",&temp);

			army[temp]=true;

		}

		for(int i=1;i<n;i++)

		{

			int from,to;

			scanf("%d%d",&from,&to);

			add(from,to);

			add(to,from);

		}

		ans=0;

		dfs(1);

		printf("%d\n",ans);

	}

	return 0;

}

方法二：SPFA

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=100000+10;

const int INF=0x3ffffff;

int head[MAXN],len,n,k;

int num[MAXN], army[MAXN];

int dis[MAXN];

bool vis[MAXN];

struct edge

{

	int to,next;

}e[MAXN<<1];

void add(int from,int to)

{

	e[len].to=to;

	e[len].next=head[from];

	head[from]=len++;

}

void spfa(int s)

{

	queue<int> q;

	for(int i=1;i<=n;i++)

	{

		dis[i]=INF;

		vis[i]=false;

	}

	q.push(s);

	dis[s]=0;

	while(!q.empty())

	{

		int cur=q.front();

		q.pop();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[id] > dis[cur] + 1)

			{

				dis[id]=dis[cur]+1;

				if(!vis[id])

				{

					q.push(id);

					vis[id]=true;

				}

			}

		}

	}

}

int main()

{

	while(~scanf("%d%d",&n,&k))

	{

		int cnt=0;

		memset(head,-1,sizeof(head));

		len=0;

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&num[i]);

			if(num[i])

				cnt++;

		}

		for(int i=0;i<k;i++)

			scanf("%d",&army[i]);

		for(int i=1;i<n;i++)

		{

			int from,to;

			scanf("%d%d",&from,&to);

			add(from,to);

			add(to,from);

		}

		int ans=0;

		for(int i=0;i<k;i++)

		{

			spfa(army[i]);

			for(int j=1;j<=n;j++)

			{

				if(!num[j] || dis[j]==INF) //不能到达或者没有叛军

					continue;

				ans+=num[j];

				num[j]=0;

				cnt--;

				if(cnt==0)

					goto next;

			}

		}

next:

		printf("%d\n",ans);

	}

	return 0;

}