CFgym100020 Problem J. Uprtof

男娘i 2021-12-05 04:41 129阅读 0赞

题意：给你n个点m无向条边。每个点是黑色或者白色的。m条边第一条边边权为2^m,第二条边边权为2^(m-1)....... 。在这个图上选择一些边连起来，使得满足：每个黑点连奇数条边，每个白点连偶数条边的条件。并且选择的边权和最小。

这是CometOJ DIV2直播上讲的一道题，大佬说的解法如下：

首先如果一个连通块的黑点个数如果是偶数，那么把黑点当做叶子节点做一下生成树，一定是满足要求的，所以如果连通块黑点个数是偶数，必然存在一个子图满足要求。而如果黑点个数是奇数，因为点的度数总和是偶数，所以必然不满足要求。按权值从大到小考虑每条边，如果去掉一条边，不改变连通性，那么这条边肯定能去掉，那么最后剩下的就是改变连通性的最小的边，也就是最小生成树上的边。因为上面的性质，可以得到，如果一条边两端的黑点个数都是偶数，那么这条边可以去掉。

所以就是先对原图求一遍最小生成森林，然后对于每棵树求出这棵树的黑点个数，然后枚举最小生成森林上的边看看是否能删去。删去条件就是删除这条边后两边的黑点个数都要是偶数，那么就可以对这棵树随便抓一个点作为树根做dfs，求出d\[i\]代表以i为根的子树的黑点个数，那么对于一条边（x，y），割去这条边之后就会变成 1，以y为根的子树 2，除去y子树的其他树。 保证这两部分黑点个数为偶数即可删去。

这里有一个小细节：一个数减去偶数后 它奇偶性不会改变，所以可以连续删。

细节看代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n,m,sum[N],fa[N],d[N],w[N];
    struct edge{ int x,y; bool used=0; }e[N<<1];
    vector<int> G[N];
    bool vis[N];
    
    int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }
    
    void Kruskal() {
        for (int i=1;i<=n;i++) fa[i]=i;
        for (int i=1;i<=m;i++) {
            int x=getfa(e[i].x),y=getfa(e[i].y);
            if (x==y) continue;
            G[e[i].x].push_back(e[i].y);
            G[e[i].y].push_back(e[i].x);
            e[i].used=1; fa[y]=fa[x];
        }
    }
    
    void dfs(int x) {
        d[x]+=w[x]; vis[x]=1;
        for (int i=0;i<G[x].size();i++) {
            int y=G[x][i];
            if (vis[y]) continue;
            dfs(y);
            d[x]+=d[y];
        }
    }
    
    int main()
    {
        freopen("uprtoff.in","r",stdin);
        freopen("uprtoff.out","w",stdout);
        cin>>n>>m;
        char s[N]; scanf("%s",s+1);
        for (int i=1;i<=n;i++) w[i]=(s[i]=='B');
        
        for (int i=1;i<=m;i++) scanf("%d%d",&e[m-i+1].x,&e[m-i+1].y);
        Kruskal();
        
        for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
        for (int i=1;i<=n;i++)
            sum[getfa(i)]=max(sum[getfa(i)],d[i]);
        for (int i=1;i<=n;i++)
            if (sum[i]%2) { puts("0"); return 0; }
        
        for (int i=m;i;i--) 
            if (e[i].used) {
                int t=min(d[e[i].x],d[e[i].y]);
                if (t%2!=0 || (sum[getfa(e[i].x)]-t)%2!=0) printf("%d ",m-i+1);
            }    
        return 0;
    }

转载于:https://www.cnblogs.com/clno1/p/10831469.html