HDU 6350 Always Online (仙人掌图，最大流)

ゝ一纸荒年。 2022-05-15 22:16 127阅读 0赞

[传送门][Link 1]

这道题真的是坑，竟然用ull，ll都会爆。

首先这是一个仙人掌图。题意让求任意两点最大流，再进行异或。先说最大流，对于环上任意两点最大流，就是两条路径最小的边和，这就等效于求出环中最小的边，使环上任意一条边都加上这条边，然后去掉最小边。这样会求出一棵树。我们将边按从大到小排序，每次向空图里加一条边（用并查集维护），那么加的这条边就是两个连通分量的最大流。

还是老方法。对于仙人掌图，（[可以看这里][Link 2]），跑一边tarjan。对于树边，直接将他放入边集里，对于环，写一个函数单独处理，去掉环中最小边，加到其他边上去。将其他边加入边集（细节在代码中注释）。

最后就是 计算异或值得问题。本来应该是n^2，枚举两个连通分量的值，但由于n太大，由于w是32位，我们可以枚举每一位，看两个联通分量中这一位有多少个0和1，能够使答案异或为1的组合的数量，就对答案贡献了多少这一位的权值。

最后注意ull

#include<cstdio>
    #include<cstring>
    #include<map>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const ll llINF=0x3f3f3f3f3f3f3f3f;
    const int N=1e5+10;
    
    struct Edg{
        int u, v, nxt;
        ll w;
    }e[N<<1], edg[N<<2], tmp[N<<1];
    
    int n, m, dfs_clock, dfn[N], low[N], head[N], cn, cnt;
    int f[N], fa[N], pos[N];//pos是用来记录该点对应的那条边，这个点是这条边的指向。
    
    ull ans;
    ll c[N][40][2];
    
    int _find(int x){
        return f[x]==x?x:f[x]=_find(f[x]);
    }
    
    void init(){
        dfs_clock=0;
        cn=0; cnt=0; ans=0;
        for(int i=1; i<=n; i++){
            head[i]=-1, dfn[i]=0;
            f[i]=i;
            for(int j=0; j<=30; j++){
                c[i][j][0]=((i>>j)&1)^1;
                c[i][j][1]=(i>>j)&1;
            }
        }
    }
    
    void addEdg(int u, int v, ll w){
        edg[cnt].u=u, edg[cnt].v=v, edg[cnt].w=w;
        edg[cnt].nxt=head[u],head[u]=cnt++;
    }
    
    void cal_cir(int fir, int las, int q){
        int num=0, id=las;
        while(id!=fir){
            tmp[++num]=edg[pos[id]];//tmp是暂时存放环上的边
            id=fa[id];
        }
        tmp[++num]=edg[q];
        ll mn=llINF;
        for(int i=1; i<=num; i++){
            if(tmp[i].w<mn){
                mn=tmp[i].w; id=i;//找最小边
            }
        }
        for(int i=1; i<=num; i++){
            if(i!=id){
                e[++cn]=tmp[i];//加入边集
                e[cn].w+=mn;
            }
        }
    }
    
    void tarjan(int u, int f){
        dfn[u]=low[u]=++dfs_clock;
        fa[u]=f;
        for(int i=head[u]; ~i; i=edg[i].nxt){
            int v=edg[i].v;
            if(v==f) continue;
    
            if(!dfn[v]) pos[v]=i, tarjan(v, u), low[u]=min(low[u], low[v]);
            else low[u]=min(low[u], dfn[v]);
        }
    
        for(int i=head[u]; ~i; i=edg[i].nxt){
            int v=edg[i].v;
            if(low[v]>dfn[u])
                e[++cn]=edg[i];//树边
            else if(dfn[v]>dfn[u]&&fa[v]!=u)
                cal_cir(u, v, i);//环
        }
    
    }
    
    bool cmp(Edg a, Edg b){
        return a.w>b.w;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%d%d", &n, &m);
            init();
            int u, v;
            ll w;
            for(int i=1; i<=m; i++){
                scanf("%d%d%lld", &u, &v, &w);
                addEdg(u, v, w);
                addEdg(v, u, w);
            }
    
            tarjan(1, -1);
    
            sort(e+1, e+1+cn, cmp);//边值排序
    
            for(int i=1; i<=cn; i++){
                int ta=_find(e[i].u), tb=_find(e[i].v);
                ll w=e[i].w;
    
                for(int j=0; j<=30; j++){
                     if (w & (1ll << j)) {
                        ans += c[ta][j][0] * c[tb][j][0] * (1ll << j);
                        ans += c[ta][j][1] * c[tb][j][1] * (1ll << j);
                    }
                    else {
                        ans += c[ta][j][0] * c[tb][j][1] * (1ll << j);
                        ans += c[ta][j][1] * c[tb][j][0] * (1ll << j);
                    }
                }
                f[ta]=tb;
                for(int j=0; j<=30; j++){
                    c[tb][j][0]+=c[ta][j][0];//将每一位的数量统计到祖先节点上
                    c[tb][j][1]+=c[ta][j][1];
                }
            }
            printf("%llu\n", ans);
        }
        return 0;
    }
    /*
    100
    3 3
    1 2 5
    2 3 6
    3 1 5
    5 4
    1 2 1
    2 3 2
    3 4 3
    4 5 4
    10 13
    1 2 1
    2 3 2
    2 4 4
    3 4 5
    4 10 8
    10 9 6
    4 9 7
    4 5 11
    5 6 13
    6 4 7
    4 7 1
    4 8 1
    7 8 1
    8 10
    1 2 1
    2 3 2
    2 4 4
    4 5 4
    4 6 4
    5 6 5
    6 7 6
    6 8 6
    7 8 7
    3 4 3
    */

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6350
[Link 2]: https://blog.csdn.net/du_lun/article/details/81482542