HDU 6350 2018HDU多校赛 第五场 Always Online（图论 + 并查集 + 组合计数）

         

 

 

大致题意：给你一个仙人掌图，让你计算：。

根据去年多校赛某一道题的经验，很多仙人掌图的问题，其实可以转化为树的问题。所以我们同样考虑，如果这是一棵树的话如何去做。注意到表达式里面的flow(i,j)表示从i到j的最小割或最大流，而在树上的最小割可以看作是两点之间连线的最短边，那么我们要做的就是统计每一条边作为最短边的贡献。这样我们不禁就联想到了之前做过的 Codeforces 915F 。这题是求任意两点之间路径上最长边减去最短边之差之和。

和那题类似，在不考虑仙人掌图，而是普通树的情况下，本题考虑对边进行排序，然后不断的并查集合并统计每条边产生的新贡献。那么我们现在考虑，当不是树的时候，根据仙人掌图的定义，每个点最多只能在一个简单环内部。我们考虑包含这样一个环的路径的最小割，这样的最小割，要么是普通路径上的一条边，要么是环中的最短边加上另一条边。具体可以参见下图：

   

我们要么切掉类似红色的边，要么切掉两条类似两条绿色的边，然后可以证明两个绿色的边一定会有一条环中流量最小的边。既然如此，如果我们找到这条边，然后把这个权值加入到环中的其他边中，然后删掉这条边，再求最小割对最后结果也不会产生影响。所以我们不妨把所有的环都这么处理，这样一个仙人掌图就会变成一棵树，我们也就可以按照之前所说的那么做了。

具体来说，如果找到这个最小的边呢。我们不妨做一遍最大生成树，这样剩下的边就一定能够与某些点构成环，而且一定是这些环中的边里面流量最小的。然后我们dfs求出fa和dep等信息，然后遍历环中的边，把每条边的权值加上这个最小流量。之后就用这个新的树新的边求解。本题需要考虑的是路径中的最小值，所以我们边也是一样从最大的开始合并。每次并查集合并，然后计算贡献。

这个贡献，由于又要考虑上两个端点i和j，所以还要有一些技巧。具体来说于 Codeforces 724G 有点类似。分别统计每一个连通块里面有多少个数在对应二进制位的值是1和0的个数。合并的时候一起合并即可。还有，最后答案比较坑，需要用到ull。具体见代码：

#include<bits/stdc++.h>
#define N 200010
#define LL long long
#define IO ios::sync_with_stdio(0);cin.tie(0)
using namespace std;

struct edge
{
    int x,y,w;

    bool operator < (const edge a) const
    {
        return w>a.w;
    }

} e[N];

int n,m,f[N],fa[N],dep[N],pre[N];
int cnt[N][32][2],sz[N][32][2];
struct Edge{int y,w;};
vector<Edge> g[N];
vector<edge> G;

int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

void dfs(int x,int ff,int d)
{
    fa[x]=ff; dep[x]=d;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i].y;
        if (y==ff) continue;
        dfs(y,x,d+1); pre[y]=i;
    }
}

void init()
{
    for(int i=1;i<N;i++)
        for(int j=0;j<31;j++)
        {
            cnt[i][j][0]=(i>>j)&1^1;
            cnt[i][j][1]=(i>>j)&1;
        }
}

int main()
{
    IO; int T;
    cin>>T; init();
    while(T--)
    {
        cin>>n>>m;
        G.clear();
        for(int i=1;i<=n;i++)
        {
            f[i]=i,g[i].clear();
            for(int j=0;j<31;j++)
            {
                sz[i][j][0]=cnt[i][j][0];
                sz[i][j][1]=cnt[i][j][1];
            }
        }
        for(int i=1;i<=m;i++)
            cin>>e[i].x>>e[i].y>>e[i].w;
        sort(e+1,e+1+m);
                                                    //kruskal
        for(int i=1;i<=m;i++)
        {
            int x=e[i].x,y=e[i].y,w=e[i].w;
            if (find(x)!=find(y))
            {
                f[find(x)]=find(y);
                g[x].push_back(Edge{y,w});
                g[y].push_back(Edge{x,w});
            } else G.push_back(edge{x,y,w});
        }
                                                    //get fa[] & pre[] & dep[]
        dfs(1,0,0);
                                                    //delete the minimum edge in the circle
        for(int i=0;i<G.size();i++)
        {
            int x=G[i].x,y=G[i].y,w=G[i].w;
            if (dep[x]<dep[y]) swap(x,y);
            for(;dep[x]>dep[y];x=fa[x])
                g[fa[x]][pre[x]].w+=w;
            for(;x!=y;x=fa[x],y=fa[y])
            {
                g[fa[x]][pre[x]].w+=w;
                g[fa[y]][pre[y]].w+=w;
            }
        }
                                                    //rebuild the graph and sort
        int tot=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<g[i].size();j++)
                if (dep[g[i][j].y]>dep[i])
                    e[++tot]=edge{i,g[i][j].y,g[i][j].w};
        sort(e+1,e+1+tot);
                                                    //initial dsu
        for(int i=1;i<=n;i++) f[i]=i;
                                                    //calculate the answer
        unsigned long long ans=0;
        for(int i=1;i<=tot;i++)
        {
            int x=e[i].x,y=e[i].y,w=e[i].w;
            x=find(x); y=find(y); f[x]=y;
            for(int j=0;j<31;j++)
            {
                if ((w&(1LL<<j))) ans+=(1LL*sz[x][j][0]*sz[y][j][0]+1LL*sz[x][j][1]*sz[y][j][1])*(1LL<<j);
                             else ans+=(1LL*sz[x][j][0]*sz[y][j][1]+1LL*sz[x][j][1]*sz[y][j][0])*(1LL<<j);
                sz[y][j][0]+=sz[x][j][0]; sz[y][j][1]+=sz[x][j][1];
            }
        }

        cout<<ans<<endl;
    }
    return 0;
}