原题： FZU 2169 http://acm.fzu.edu.cn/problem.php?pid=2169
这题貌似有两种解法，DFS和SPFA，但是DFS怎么都RE，SPFA也要用邻接表表示边，用向量表示的话会TLE，而且用SPFA有一个异或，就是题目说要沿最短路走到都城，但是SPFA是走最短路去消灭叛军，然后再走回都城，我不知道怎么回事，不知道能不能有大神解释。因为这样的话，有多少叛军就能消灭多少叛军了，那就不要用什么算法 了，直接一个统计。于是试了一下，居然A了，瞬间变成大水题，我无法再评价这个题目了，就当消遣了。
SPFA法：依次从每个军队城市出发做一次SPFA，看到有能到的（肯定能到啊）叛军就将其消灭。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #define Mod 1000000007 using namespace std; #define N 100007 struct Edge { int v,next; }G[2*N]; int head[N],tot; int army[N],rebel[N]; int vis[N],dis[N]; int res; int n,m; void addedge(int u,int v) { G[tot].v = v; G[tot].next = head[u]; head[u] = tot++; } void SPFA(int s) { int i; memset(vis,0,sizeof(vis)); queue<int> que; while(!que.empty()) que.pop(); que.push(s); vis[s] = 1; dis[s] = 0; while(!que.empty()) { int tmp = que.front(); que.pop(); vis[tmp] = 0; for(i=head[tmp];i!=-1;i=G[i].next) { int v = G[i].v; if(dis[v] > dis[tmp] + 1) { dis[v] = dis[tmp]+1; if(!vis[v]) { que.push(v); vis[v] = 1; } } } } } int main() { int i,j,x; int u,v; while(scanf("%d%d",&n,&m)!=EOF) { memset(army,0,sizeof(army)); memset(rebel,0,sizeof(rebel)); memset(head,-1,sizeof(head)); tot = 0; int cnt = 0; for(i=1;i<=n;i++) { scanf("%d",&rebel[i]); if(rebel[i]) cnt++; } for(i=1;i<=m;i++) scanf("%d",&army[i]); for(i=0;i<n-1;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } res = 0; for(i=1;i<=m;i++) { SPFA(army[i]); for(j=1;j<=n;j++) { if(dis[j] != Mod) { if(rebel[j]) { res += rebel[j]; rebel[j] = 0; cnt--; } } } if(cnt == 0) //已经消灭完 break; } printf("%d ",res); } return 0; }
DFS法（选GNU C++ 会Runtime Error，要选Visual C++）：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #define Mod 1000000007 #define ll long long using namespace std; #define N 100007 struct Edge { int v,next; }G[2*N]; int head[N],tot; int army[N],rebel[N]; ll sum; int n,m; void addedge(int u,int v) { G[tot].v = v; G[tot].next = head[u]; head[u] = tot++; } int dfs(int u,int val,int fa) { int soni = 0; if(army[u]) //找到军队 { sum += val; soni++; } for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; soni += dfs(v,val+rebel[u],u); } if(soni > 1) sum -= (soni-1)*rebel[u]; return soni; } int main() { int i,j,x; int u,v; while(scanf("%d%d",&n,&m)!=EOF) { memset(army,0,sizeof(army)); memset(rebel,0,sizeof(rebel)); memset(head,-1,sizeof(head)); tot = 0; for(i=1;i<=n;i++) scanf("%d",&rebel[i]); for(i=1;i<=m;i++) { scanf("%d",&x); army[x] = 1; } for(i=0;i<n-1;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } sum = 0; dfs(1,0,-1); printf("%lld ",sum); } return 0; }
直接统计：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; #define N 100007 int army[N],rebel[N]; int res; int n,m; int main() { int i,j,x; int u,v; while(scanf("%d%d",&n,&m)!=EOF) { memset(rebel,0,sizeof(rebel)); int cnt = 0; res = 0; for(i=1;i<=n;i++) { scanf("%d",&rebel[i]); if(rebel[i]) res += rebel[i]; } for(i=1;i<=m;i++) scanf("%d",&army[i]); for(i=0;i<n-1;i++) scanf("%d%d",&u,&v); if(m == 0) { puts("0"); continue; } printf("%d ",res); } return 0; }