E. Minimum spanning tree for each edge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains n vertices and m edges.
For each edge (u, v) find the minimal possible weight of the spanning tree that contains the edge (u, v).
The weight of the spanning tree is the sum of weights of all edges included in spanning tree.
Input
First line contains two integers n and m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — the number of vertices and edges in graph.
Each of the next m lines contains three integers ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — the endpoints of the i-th edge and its weight.
Output
Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.
The edges are numbered from 1 to m in order of their appearing in input.
Sample test(s)
input
5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4
output
9
8
11
8
8
8
9
题意：给出一个图，问每一条边如果要在一个生成树当中，那这个生成树最小是多少。
分析：先找出一个最小生成树。
想像一下，加入一条边，会对这个生成树造成什么影响。
形成了一个环，然后最优情况，肯定要拿掉除他之外最大的一条边。
问题就变成了，在最小生成树上查询两点之间的边的最大值。
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mk make_pair inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = , M = ;
int n, m;
struct EdgeType
{
int u, v, value, index;
LL ans;
inline bool operator <(const EdgeType &t) const
{
return value < t.value;
} inline void Read()
{
u = Getint();
v = Getint();
value = Getint();
}
} edge[N];
int fa[N], favalue[N];
int first[N], to[N * ], value[N * ], next[N * ], tot;
int up[N][M], depth[N], maxcnt[N][M];
LL ans; inline void Input()
{
n = Getint();
m = Getint();
for(int i = ; i <= m; i++)
{
edge[i].Read();
edge[i].index = i;
}
} inline int Find(int x)
{
static int path[N], len;
for(len = ; x != fa[x]; x = fa[x])
path[++len] = x;
for(int i = ; i <= len; i++) fa[path[i]] = x;
return x;
} inline void Insert(int u, int v, int val)
{
tot++;
to[tot] = v, value[tot] = val, next[tot] = first[u];
first[u] = tot;
} inline void Bfs()
{
static int que[N], head, tail;
for(int i = ; i <= n; i++) fa[i] = -;
que[] = , head = tail = , fa[] = , depth[] = ;
while(head <= tail)
{
int u = que[head++];
for(int tab = first[u], v; tab; tab = next[tab])
if(fa[v = to[tab]] == -)
{
fa[v] = u, favalue[v] = value[tab], depth[v] = depth[u] + ;
que[++tail] = v;
}
}
} inline int GetMax(int u, int v)
{
int ret = , level = M;
while(depth[u] != depth[v])
{
if(depth[u] < depth[v]) swap(u, v);
while(level && ( << level) > depth[u] - depth[v]) level--;
ret = max(ret, maxcnt[u][level]);
u = up[u][level];
}
level = M;
while(level && u != v)
{
while(level && ( << level) > depth[u]) level--;
while(level && up[u][level] == up[v][level]) level--;
ret = max(ret, maxcnt[u][level]);
ret = max(ret, maxcnt[v][level]);
u = up[u][level], v = up[v][level];
}
while(u != v)
{
ret = max(ret, favalue[u]);
ret = max(ret, favalue[v]);
u = fa[u], v = fa[v];
}
return ret;
} inline bool CompareByIndex(const EdgeType &a, const EdgeType &b)
{
return a.index < b.index;
} inline void Solve()
{
sort(edge + , edge + + m);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++)
{
int u = Find(edge[i].u), v = Find(edge[i].v);
if(u != v)
{
Insert(edge[i].u, edge[i].v, edge[i].value);
Insert(edge[i].v, edge[i].u, edge[i].value);
ans += edge[i].value;
fa[u] = v;
}
} Bfs(); for(int i = ; i < M; i++)
{
if(( << i) > n) break;
for(int j = ; j <= n; j++)
if(i == )
{
up[j][i] = fa[j];
maxcnt[j][i] = favalue[j];
}
else
{
up[j][i] = up[up[j][i - ]][i - ];
maxcnt[j][i] = max(maxcnt[j][i - ], maxcnt[up[j][i - ]][i - ]);
}
} for(int i = ; i <= m; i++)
{
int u = edge[i].u, v = edge[i].v;
int ret = GetMax(u, v);
edge[i].ans = ans - ret + edge[i].value;
} sort(edge + , edge + + m, CompareByIndex);
for(int i = ; i <= m; i++) printf("%I64d\n", edge[i].ans);
} int main()
{
freopen("a.in", "r", stdin);
Input();
Solve();
return ;
}
