FZU2169 shadow题解

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

题意：N<=10万个点，N-1条边使所有点连通，点编号为1~N，1号点为国王所在地，给出K个编号表示这K个点有国王的军队，给出Ai表示第i个点有Ai个叛军，国王所在地和有国王军的地方没叛军。现在国王的军队以最短路向国王所在地移动，消灭沿途所有叛军，求消灭的叛军数。

解：用STL的set记国王军所在地，从国王所在地开始宽搜，从当前点u扩展节点时记录扩展节点v来自哪里，from[v]=u。搜到一个国王军就把之前走的这条路上的点的叛军数加到ans里，并且对沿途的点标记geted[x]=true，一开始先标记国王所在地geted[0]=true，这样每次找到一个国王军就把国王军到geted为true的点之间的叛军数加到ans里，并且统计找到的国王军数cnt++。cnt==K时就找够全部国王军了，结束。是不是很碉，只要一次宽搜就得了耶！

 #include<iostream>
 #include <cstdio>
 #include <cstring>
 #include <cstdlib>
 #include<vector>
 #include<queue>
 #include<set>
 #define MAXN 101111
 #define RE freopen("in.txt","r",stdin); using namespace std; struct Edge
 {
     int u,v;
     int next;
 };
 Edge e[MAXN*];
 int first[MAXN];
 int en; void add(int u,int v)
 {
     e[en].u=u;
     e[en].v=v;
     e[en].next=first[u];
     first[u]=en;
     en++;
 } int n,k,cnt;
 int a[MAXN];
 set<int> b;
 bool walked[MAXN];
 bool geted[MAXN];
 queue<int> v;
 int from[MAXN];
 int farm();
 void init(); int main()
 {
     //RE
     while(scanf("%d%d",&n,&k)!=EOF)
     {
         farm();
     }
     return ;
 } int farm()
 {
     int i,j,x,y;
     init();
     for(i=; i<n; i++)
         scanf("%d",&a[i]);
     for(i=; i<k; i++)
     {
         scanf("%d",&x);
         x--;
         b.insert(x);
     }
     for(i=; i<n-; i++)
     {
         scanf("%d%d",&x,&y);
         x--;y--;
         add(y,x);
         add(x,y);
     }
     long long ans=;
     while(!v.empty()) v.pop();
     v.push();
     walked[]==true;
     geted[]=true;
     while(!v.empty())
     {
         int now=v.front();
         v.pop();
         //cout<<now<<'!';
         if(b.find(now)!=b.end())
         {
             //cout<<now<<',';
             x=now;
             while(!geted[x])
             {
                 geted[x]=true;
                 ans+=a[x];
                 x=from[x];
             }
             cnt++;
             if(cnt==k) break;
             continue;
         }
         for(j=first[now]; j!=-; j=e[j].next)
         {
             //cout<<j<<'?';
             int next=e[j].v;
             if(!walked[next])
             {
                 walked[next]=true;
                 v.push(next);
                 from[next]=now;
             }
         }
     }
     printf("%lld\n",ans);
     return ;
 } void init()
 {
     memset(e,,sizeof(e));
     memset(first,-,sizeof(first));
     memset(walked,false,sizeof(walked));
     memset(geted,false,sizeof(geted));
     b.clear();
     cnt=;
     en=;
 }

话说我交的时候突然想起set没清空，不过还是过了，难道只有一组数据…

不过耗时好像比其他方法久……好像可以手动开栈 深搜，我也不太懂怎么弄的