Ponds （并查集||拓扑+深搜）

Ponds

题意

给你n个点，m条无向边，每个点有vi的价值，你必须尽可能删去点，要求是删去的点的度数必须小于2。问你最后每个连通图中剩余奇数个点的总价值？

思路

1、一开始想是并查集吧，因为要计算每个环的点的数量，先把所有能删的点删去之后，再把剩下的边union起来，计算每个父亲所拥有的子的个数，奇数就加上去……

2、拓扑+深搜。应该还是把能删掉的点先删掉，然后深搜也是找环的点数。

看！代码

/**
	并查集做法
	*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=0x3f3f3f3f;
const int N = 1e4+10;
struct node{
    vector<int>next;
    int deg;
    int id;
    node()
    {
        deg=0;
    }
};
int id[N];
int sz[N];

ll poor[N];
int vis[N];
int cnt[N];
int edge[N][2];
int Find(int x)  ///找跟根结点
{
    while(x!=id[x])
    {
        id[x]=id[id[x]];
        x=id[x];
    }
    return x;
}

int un(int p,int q)
{
    int pr=Find(p);
    int qr=Find(q);
    if(pr==qr) return -1;
    if(sz[pr]<=sz[qr])
    {
        sz[qr]+=sz[pr];id[pr]=qr;
    }
    else
    {
        sz[pr]+=sz[qr];id[qr]=pr;
    }
}

void clear()
{
    for(int i=1;i<=N;i++)
    {
        id[i]=i;sz[i]=1;
    }
}

int main()
{
    int t;
    int p,m,u,v;
    scanf("%d",&t);
    while(t--)
    {
        node x[N];
        memset(vis,0,sizeof(vis));
        memset(cnt,0,sizeof(cnt));
        clear();

        scanf("%d%d",&p,&m);
        for(int i=1;i<=p;i++)
            scanf("%lld",&poor[i]);

        for(int i=1;i<=p;i++)
            x[i].id=i;

        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            x[u].next.push_back(v);
            x[u].deg++;
            x[v].next.push_back(u);
            x[v].deg++;
            edge[i][0]=u;
            edge[i][1]=v;
        }
        queue<node>q;
        for(int i=1;i<=p;i++)
            if(x[i].deg==1)
                q.push(x[i]);
            else if(x[i].deg==0)
                vis[i]=1;
        node temp;
        while(!q.empty())
        {
            temp=q.front();
            q.pop();
            vis[temp.id]=1;
            for(int i=0;i<temp.next.size();i++)
                if(!vis[temp.next[i]])
            {
                x[temp.next[i]].deg--;
                if(x[temp.next[i]].deg==1)
                    q.push(x[temp.next[i]]);
                else if(x[temp.next[i]].deg==0)
                    vis[x[temp.next[i]].id]=1;
            }
        }

        for(int i=0;i<m;i++)
        {
            int x=edge[i][0],y=edge[i][1];
            if(vis[x]==1||vis[y]==1)continue;
            un(x,y);
        }
        for(int i=1;i<=p;i++)
        {
            if(vis[i]==0)
                cnt[Find(i)]++;
        }

        long long ans=0;
        for(int i=1;i<=p;i++)
        {
            if(vis[i]==0&&cnt[Find(i)]>=3&&cnt[Find(i)]%2==1)
                ans+=poor[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}