首页 > 代码库 > shadow

shadow

2024-08-09 18:48:02   218人阅读

Description：

YL是shadow国的国王,shadow国有N个城市。为了节省开支,shadow国只有N-1条道路,这N-1条道路使得N个城市连通。某一年,shadow国发生了叛乱,叛军占领了多个城市,王都岌岌可危。王都为编号为1的城市，除了王都外有K个城市有YL的军队。现在这K支军队要向王都进军，并且消灭沿途经过的城市中的叛军。现给出N个城市的道路情况以及城市的叛军数量，问总共需要消灭多少叛军？


Input

第一行输入两个整数N，K，接下来输入N(1<=N<=100000)个整数Ai(0<=Ai<=10000)，表示第i个城市的叛军数量。接下来输入K个大于等于1且小于等于N的整数，表示有军队的城市的编号。数据保证王都以及有军队的城市没有叛军。接下来输入N-1行，每行两个整数u、v，表示连接u和v的一条道路。每支军队只能沿着道路走，并且是其所在城市与王都之间的最短路线走。


Output

输出一行一个整数表示消灭的叛军数量。


Sample Input：

4 2
0 3 0 0
3 4
1 2
2 3
2 4

Sample Output：

3


<span style="font-size:18px;"># include <cstdio>
# include <queue>
# include <cstring>
# include <iostream>
using namespace std;

const int maxn=110000;
const int INF=1<<30;
int dis[maxn],head[maxn],vis[maxn],path[maxn],s[maxn],ss[maxn];
//head[i] 表示的是：以i边为起点的边最后一次出现，是第几条边；
//e[x].next的值表示的是；在这条边之前，有没有出现过以x为起点
//的边，有的话就是序号，没有的话就是-1；
struct Edges
{
    int x,y,w,next;

}e[maxn<<2];

void AddEdge(int x,int y,int w,int k)
{
    e[k].x=x,e[k].y=y,e[k].w=w,e[k].next=head[x],head[x]=k;
}

int relax(int u,int v,int c)      //判断能否更新两点之间的距离
{
    if(dis[v] > dis[u] + c)
    {
        dis[v]=dis[u]+c;
        path[v]=u;
        return 1;
    }
    return 0;
}

int SPFA(int src)
{
    int i;
    memset(vis,0,sizeof(vis));
    dis[src]=0;
    queue <int> q;
    vis[src]=1;
    q.push(src);
    while(!q.empty())
    {
        int u,v,i;
        u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u]; i!=-1 ;i=e[i].next )
        {
            v = e[i].y;
            if(relax(u,v,e[i].w)==1&&!vis[v])    //判断是否更新成功&&是否已经在队列中；
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return 0;
}

int main()
{
    //freopen("a.txt","r",stdin);
    int n,k,i;
    while(~scanf("%d%d",&n,&k))
    {
        memset(e,-1,sizeof(e));
        memset(path,-1,sizeof(path));
        for(i=1;i<=n;i++)
        {
            dis[i]=INF;
            head[i]=-1;
        }
        int cnt=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            if(s[i])   cnt++;
        }
        for(i=1;i<=k;i++)   scanf("%d",&ss[i]);

        for(i=0;i<(n-1)*2;i+=2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            AddEdge(x,y,1,i);
            AddEdge(y,x,1,i+1);
        }
        SPFA(1);
        int ans=0;
        for(i=1;i<=k;i++)
        {
            int p=path[ss[i]];
            while(p!=1&&p!=-1)
            {
                if(s[p])    { ans+=s[p]; cnt--;   s[p]=0;}
                p=path[p];
            }
            if(!cnt)    break;
        }
        printf("%d\n",ans);
    }
    return 0;
}</span>



shadow


联系
我们