HDU5438--Ponds (拓排+BFS)

点击打开链接

题意：给定n个池塘，m对池塘相连，现在要将与少于2个池塘相连的池塘拆除，形成森林，求节点数为奇数的树权值之和

思路：按照拓排的思想不断删除度数小于2的节点

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e4+5;

vector <ll> G[N];

queue <ll> Q;//拓排队列

queue <ll> P;//BFS队列

bool visit[N];//符合条件的点

ll value[N];

ll vis[N];//bfs遍历过的点

ll degree[N];//度数

ll m,n,ans;

void topsort()

{

    while(!Q.empty()) Q.pop();

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

    {

        if(degree[i]<2)

        {

            if(degree[i]==1) Q.push(i);

            visit[i]=1;

        }

    }

    while(!Q.empty())

    {

        ll temp=Q.front();

        Q.pop();

        int len=G[temp].size();

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

        {

            if(--degree[G[temp][i]]<2)

            {

                if(degree[G[temp][i]]==1) Q.push(G[temp][i]);

                visit[G[temp][i]]=1;

            }

        }

    }

}

ll bfs(int x)

{

    ll sum=value[x],num=1;

    P.push(x);

    vis[x]=1;

    while(!P.empty())

    {

        ll temp=P.front();

        P.pop();

        int len=G[temp].size();

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

        {

            if(!vis[G[temp][i]]&&!visit[G[temp][i]])

            {

                P.push(G[temp][i]);

                vis[G[temp][i]]=1;

                num++;

                sum+=value[G[temp][i]];

            }

        }

    }

    if(num&1) return sum;

    return 0;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

        memset(visit,0,sizeof(visit));

        memset(degree,0,sizeof(degree));

        scanf("%lld%lld",&n,&m);

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

            scanf("%lld",&value[i]);

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

            G[i].clear();

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

        {

            int x,y;

            scanf("%d%d",&x,&y);

            degree[x]++;

            degree[y]++;

            G[x].push_back(y);

            G[y].push_back(x);

        }

        topsort();

        ans=0;

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

        {

            if(!vis[i]&&!visit[i])

                ans+=bfs(i);

        }

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

    }

    return 0;

}