本校网络赛某一题。豪哥用动态mst来形容。
题解：对一个mst，随便新加入的边，求更优的mst
每个mst中的子mst可能构成不同，但值一定不变，那么新边e[u,v]的加入，将mst分成三部分，以u跟v之间割为一份M，mst去掉M后以u为根的U，和以v为根的V。
e[u,v]对U跟V没影响，只影响了M（M跟e肯定构成环H），所以只需要在H中寻找最大的边删除即可。
#include <stdio.h>
#include <stdlib.h>
#define inf 1000000000
#define maxn 1010
int dis[maxn], visit[maxn], map[maxn][maxn], path[maxn], hash[maxn][maxn];
int n, flag, th;
struct T
{
int u, v, w, next;
}fn[maxn * maxn];
struct R
{
int v, w;
}p[maxn];
int g[maxn];
void Set()
{
int i, j;
for (i = 0; i <= n; i++)
{
dis[i] = inf, visit[i] = 0, path[i] = 0, g[i] = -1;
}
}
//无向图邻接表加边
void add(int u, int v, int w)
{
fn[th].u = u, fn[th].v = v, fn[th].next = g[u], fn[th].w = w, g[u] = th++;
fn[th].u = v, fn[th].v = u, fn[th].next = g[v], fn[th].w = w, g[v] = th++;
}
//无向图邻接表删边
void del(int u, int v)
{
int i, j;
i = g[u];
if (i != -1)
{
if (fn[i].v == v)
{
g[u] = fn[i].next;
}
else
{
for (j = fn[i].next; j != -1; j = fn[j].next, i = fn[i].next)
{
if (fn[j].v == v)
{
fn[i].next = fn[j].next;
break;
}
}
}
}
i = g[v];
if (i != -1)
{
if (fn[i].v == u)
{
g[v] = fn[i].next;
}
else
{
for (j = fn[i].next; j != -1; j = fn[j].next, i = fn[i].next)
{
if (fn[j].v == u)
{
fn[i].next = fn[j].next;
break;
}
}
}
}
}
//邻接矩阵普利姆
int Prime()
{
Set();
int i, j, pre, next, sum = 0, min;
for (i = 0, pre = 1; i < n - 1; i++)
{
visit[pre] = 1, min = inf;
for (j = 1; j <= n; j++)
{
if (visit[j] == 0)
{
if (dis[j] > map[pre][j])
{
dis[j] = map[pre][j];
path[j] = pre;//更新或保存j在mst中的父节点
}
if (min > dis[j])
{
min = dis[j];
next = j;
}
}
}
pre = next;
sum += dis[pre];
}
for (i = 1; i <= n; i++)
{
if (path[i])//hash用来判断hash[i][j]是否是mst的边
{
hash[i][path[i]] = hash[path[i]][i] = 1;
}
}
for (i = 1; i <= n; i++)//将mst用邻接表重新构图
{
for (j = 1; j < i; j++)
{
if (hash[i][j])
{
add(i, j, map[i][j]);
}
}
}
return sum;
}
inline void dfs(int u)
{
visit[u] = 1;
int i;
for (i = 1; i <= n; i++)
{
if (!visit[i] && map[u][i] != inf)
{
dfs(i);
}
}
}
void find(int u, int f)//邻接表mst中搜寻u到f之间的边
{
visit[u] = 1;
if (u == f)
{
flag = 1;
return;
}
int i, v;
for (i = g[u]; i != -1; i = fn[i].next)
{
v = fn[i].v;
if (!visit[v])
{
p[v].v = u, p[v].w = fn[i].w;
find(v, f);
if (flag)
{
return;
}
}
}
}
void show()
{
int i, j;
for (i = 1; i <= n; i++)
{
printf("%d:", i);
for (j = g[i]; j != -1; j = fn[j].next)
{
printf(" [%d,%d]", fn[j].v, fn[j].w);
}
printf("\n");
}
}
int main()
{
//freopen("net.in", "r", stdin);
//freopen("ex.out", "w", stdout);
int t, m, i, j, sign, u, v, w, sum, ca = 0;
scanf("%d", &t);
while (t--)
{
ca++;
th = 0;
printf("Case %d:\n", ca);
scanf("%d%d", &n, &m);
sign = 1;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
map[i][j] = inf, hash[i][j] = 0;
}
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
if (sign)//图没连同时，继续加边并判断加边后是否连同，如果是，求mst并用邻接表重构mst
{
if (map[u][v] > w)
{
map[u][v] = map[v][u] = w;
for (i = 1; i <= n; i++) visit[i] = 0;
dfs(1);
for (i = 1; i <= n && visit[i]; i++);
if (i == n + 1)
{
sign = 0;
sum = Prime();
}
}
if (sign)
{
printf("The net still undone\n");
}
else
{
printf("%d\n", sum);
}
}
else//图已连同，则完后所有加边，图都是连同的，树课随着加入的边调整，是mst的值更小
{
flag = 0;
for (i = 1; i <= n; i++)
{
visit[i] = 0, p[i].v = -1;
}
find(u, v);
for (i = v, j = v; i != u; i = p[i].v) //在u跟v直接寻找最大边。因为用find(u,v),所以i的前驱节点为path[i].v
{
if (p[j].w < p[i].w)
{
j = i;
}
}
if (p[j].w > w)
{
sum = sum - p[j].w + w;
del(j, p[j].v);
add(u, v, w);
}
printf("%d\n", sum);
}
}
}
return 0;
}
/*
10
4 10
1 2 1
2 3 3
1 3 1
3 4 1
2 3 3
2 3 0
5 6
1 2 5
2 3 1
2 4 4
2 5 3
1 2 3
1 4 1
*/