这份代码RE，待调

Problem

Description

给一张仙人掌图，求

$\sum(i \otimes j \otimes maxflow(i,j))$

$\otimes$ 表示异或

Input

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains two integers n and m.

Each of the following m lines contains three integers u, v and w, indicating a bidirectional edge between vertex u and vertex v that can transmit at most w bits per second in each direction.

It is guaranteed that the sum of n in all test cases does not exceed 106 and the size of the standard input file does not exceed 26 MiB.

Output

For each test case, print the answer in one line.

Sample Input

Sample Output

27
116

HINT

Solution

Analysis

问题一：考虑对于一棵树，我们只需要从大到小插入边就可以统计$maxflow$。

问题二：对于仙人掌，我们考虑对于环该如何操作，环的$maxflow$是两条的$maxflow$，我们可以通过将这个环上的最小边破开

将最小边的权值加入到其他边上，转换为问题一。

Attention

尚不明确为什么RE

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
typedef long long ll;
const int N=1e5+10,M=2e5+10;
using namespace std;
struct Edge{
    int u,v;
    ll w;
    int nxt;
    il bool operator <(const Edge &other) const{
        return w>other.w;
    }
} e[M],edge[M<<1],tmp[M];int head[N],tot,cnt;
il void add_edge(int u,int v,ll w){
    ++tot;
    e[tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].nxt=head[u];
    head[u]=tot;
}
int n,m;
namespace find_union{
    int fa[N];
    il void init(){ rep(i,1,n) fa[i]=i;}
    il int find(int x){ if(x==fa[x]) return x;return fa[x]=find(fa[x]);}
    il void merge(int x,int y){ fa[y]=x;}
}
int dfs_clock,dfn[N],low[N],fa[N],from[N];
il void circle(int u,int v,int lst){
    int num=0;
    while(v!=u){
        tmp[++num]=e[from[v]];
        v=fa[v];
    }
    tmp[++num]=e[lst];
    ll res=LLONG_MAX;
    rep(i,1,num){
        if(tmp[i].w<res){
            res=tmp[i].w;
            v=i;
        }
    }
    rep(i,1,num){
        if(i==v) continue;
        edge[++cnt]=tmp[i];
        edge[cnt].w+=res;
    }
}
il void tarjan(int u,int f){
    dfn[u]=low[u]=++dfs_clock;
    fa[u]=f;
    for(register int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==f) continue;
        if(!dfn[v]){ from[v]=i;tarjan(v,u);low[u]=min(low[u],low[v]);}
        else low[u]=min(low[u],dfn[v]);
    }
    for(register int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(low[v]>dfn[u]) edge[++cnt]=e[i];
        else if(dfn[v]>dfn[u] && fa[v]!=u) circle(u,v,i);
    }
//    cerr<<u<<' '<<dfn[u]<<' '<<low[u]<<endl;
}
unsigned long long ans,c[N][31][2];
il void init(){
    dfs_clock=tot=cnt=0;
    ans=0;
    find_union::init();
    rep(i,1,n){
        head[i]=dfn[i]=low[i]=fa[i]=0;
        rep(j,0,30){
            c[i][j][0]=((i>>j)&1)^1;
            c[i][j][1]=c[i][j][0]^1;
        }
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,1,m){
            int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);
            add_edge(u,v,w);
            add_edge(v,u,w);
        }
        tarjan(1,-1);
        sort(edge+1,edge+1+cnt);
        rep(i,1,cnt){
            int fu=find_union::find(edge[i].u);
            int fv=find_union::find(edge[i].v);
            ll w=edge[i].w;
            rep(j,0,30){
                ll k=(w&(1ll<<j));
                k=bool(k);
                ans+=c[fu][j][0]*c[fv][j][k^1]*(1ll<<j);
                ans+=c[fu][j][1]*c[fv][j][k]*(1ll<<j);
            //    cerr<<fv<<' '<<j<<' '<<c[fv][j][0]<<' '<<c[fv][j][1]<<endl;
            }
        //    cerr<<ans<<endl;
            find_union::merge(fu,fv);
            rep(j,0,30){
                c[fu][j][0]+=c[fv][j][0];
                c[fu][j][1]+=c[fv][j][1];
            }
        }
        printf("%llu\n",ans);
    }
    return 0;
}

gym102114A