省略
省略
C++に変換後のコードはこちら
int N, M, A[1d5], B[1d5], C[1d5], ind[1d5];
ll res[1d5];
wgraph<int> g;
HLD hld;
HLD_segtree<int> t;
int mm, aa[1d5], bb[1d5], cc[1d5];
int val[1d5];
{
int i, x;
unionFind uf;
ll bas = 0;
rd(N,M,(A--,B--,C)(M));
rep(i,M) ind[i] = i;
sortA(M,C,A,B,ind);
uf.walloc(N, 1);
rep(i,M) if(uf(A[i],B[i])){
arrInsert(mm, mm, aa, A[i], bb, B[i], cc, C[i]);
bas += C[i];
}
g.setEdge(N, mm, aa, bb, cc);
hld.init(g.g);
rep(i,mm){
x = if[hld.depth(aa[i]) > hld.depth(bb[i]), aa[i], bb[i]];
val[x] = -cc[i];
}
t.init(&hld, val);
rep(i,M) res[ind[i]] = bas + C[i] + t.getMinVal_edge(A[i], B[i]);
wtLn(res(M));
}
Current time: 2024年04月20日15時28分24秒
Last modified: 2021年01月02日17時04分59秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)