【LightOJ - 1123】Trail Maintenance（在线维护最小生成树，删边思维）

题干：

Tigers in the Sunderbans wish to travel freely among the N fields (numbered from 1 to N), even though they are separated by trees. The tigers wish to maintain trails between pairs of fields so that they can travel from any field to any other field using the maintained trails. Tigers may travel along a maintained trail in either direction.

The tigers do not build trails. Instead, they maintain deer trails that they have discovered. On any week, they can choose to maintain any or all of the deer animal trails they know about. Always curious, the tigers discover one new deer trail at the beginning of each week. They must then decide the set of trails to maintain for that week so that they can travel from any field to any other field. Tigers can only use trails which they are currently maintaining.

The tigers always want to minimize the total length of trail they must maintain. The tigers can choose to maintain any subset of the deer trails they know about, regardless of which trails were maintained the previous week. Deer trails (even when maintained) are never straight. Two trails that connect the same two fields might have different lengths. While two trails might cross, tigers are so focused; they refuse to switch trails except when they are in a field. At the beginning of each week, the tigers will describe the deer trail they discovered. Your program must then output the minimum total length of trail the tigers must maintain that week so that they can travel from any field to any other field, if there is such a set of trails.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case starts with two integers N (1 ≤ N ≤ 200) and W. W is the number of weeks the program will cover (1 ≤ W ≤ 6000).

Each of the next W lines will contain three integers describing the trail the tigers found that week. The first two numbers denote the end points (filed numbers) and the third number denotes the length of the trail (1 to 10000). No trail has the same field as both of its end points.

Output

For each case, print the case number in a line. Then for every week, output a single line with the minimum total length of trail the tigers must maintain so that they can travel from any field to any other field. If no set of trails allows the tigers to travel from any field to any other field, output "-1".

Sample Input

4 6

1 2 10

1 3 8

3 2 3

1 4 3

1 3 6

2 1 2

Sample Output

Case 1:

-1

题目大意：

n个点，m个边顺序添加，每次添加，要求在线输出MST的权值，如果凑不出MST就输出-1。

解题报告：

直接暴力肯定会超时。

考虑到n只有200：因为最差情况：大于n条边的时候，肯定会生成一个环，那么最终生成环的这一条边，肯定是我们最后遍历到的，而恰好肯定是环内权值最大的（因为按边权排序了之后再遍历的。），所以这一条边可以直接扔掉（简化操作就是记录一下这个边的位置，然后遍历结束后把最后一条边直接赋值过来。）

下面给出简要证明：为什么这一条边e一定不会要，也就是，不管后面的边如何添加的，这一条边一定没用了（也就是一定不会是MST中的边）：因为每次加边操作都是只加一条，所以最多替换一条边，考虑每次替换边，都是去掉一条边w1，换上一条边w2，那么这个替换执行当且仅当w1>w2，也就是新边的权值肯定要更小，我们才考虑替换他。由上一段的分析得知，这条边e的权值we>w1，所以这一条边we>w2，所以肯定这条边没用了。因为他只要是棵树，我们不需要看边选的是啥，因为可以确定的是，树上的点一定就是那一些，所以具体哪些边没影响。至此，我们可以放心大胆的删掉这条边了。

这次是体会到了常数的可怕。。。把自定义比较函数放在结构体内部确实是快（160ms级别和240ms级别的区别。）另外getf也是这样，uv直接变成祖先节点才能冲进200ms，不然就是200多ms。不过如果不卡并查集的话问题就不大。

另外对于这题，不能加cnt==n-1则break。因为可能需要删除的边在后面。总之这一点可以被卡。所以要注意。不过其实最多稳定在200条边，所以加不加这个优化影响不大。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int f[222];
struct Edge {
	int u,v,w;
	bool operator<(const Edge b) const {
		return w < b.w;
	}
} e[MAX];
int tot,n,m;
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
void init() {
	for(int i = 1; i<=n; i++) f[i] = i;
}
int klu() {
	sort(e+1,e+tot+1);
	int cnt = 0,pos=-1,res = 0;
	for(int i = 1; i<=tot; i++) {
		int u = getf(e[i].u),v = getf(e[i].v);
		if(u==v) pos = i;
		else {
			f[v]=u;
			res += e[i].w;
			cnt++;
		}
//		if(cnt == n-1) break; 
	} 
	if(pos != -1) {
		e[pos] = e[tot];
		tot--;
	}
	if(cnt == n-1) return res;
	else return -1;
}
int main()
{
	int t,iCase = 0;
	scanf("%d",&t);
	while(t--) {
		printf("Case %d:\n",++iCase);
		tot=0;
		scanf("%d%d",&n,&m);
		for(int a,b,c,i = 1; i<=m; i++) {
			scanf("%d%d%d",&a,&b,&c);
			e[++tot].u = a;e[tot].v = b;e[tot].w = c;
			init();
			printf("%d\n",klu());
		}
	}


	return 0 ;
}

换了一种优化反而更慢（161ms）注意这样写的话要提前赋值tot给tott，并且遍历边的时候还是遍历到tott。因为你后面的那些边虽然可能要删除，但是前提是在你找到MST的时候，你在线就tot--了，可能人家本来就是第tot条边凑出MST，但是你这样操作就输出-1了。

总结一下这样慢的原因，其实没必要加那个cnt==n-1就break。因为本来边就不多，动态稳定在n-1附近，，所以没必要，，因为反而增加了很多次if判断，所以耗时了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int f[222];
struct Edge {
	int u,v,w;
	bool operator<(const Edge b) const {
		return w < b.w;
	}
} e[MAX];
int tot,n,m;
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
void init() {
	for(int i = 1; i<=n; i++) f[i] = i;
}
int klu() {
	sort(e+1,e+tot+1);
	int cnt = 0,pos=-1,res = 0,tott=tot;
	for(int i = 1; i<=tott; i++) {
		int u = getf(e[i].u),v = getf(e[i].v);
		if(u==v) {
			e[i] = e[tot];
			tot--;
		}
		else {
			f[v]=u;
			res += e[i].w;
			cnt++;
		}
		if(cnt == n-1) {
			tot=i;
			break; 
		}
	} 
//	if(pos != -1) {
//		e[pos] = e[tot];
//		tot--;
//	}
	if(cnt == n-1) return res;
	else return -1;
}
int main()
{
	int t,iCase = 0;
	scanf("%d",&t);
	while(t--) {
		printf("Case %d:\n",++iCase);
		tot=0;
		scanf("%d%d",&n,&m);
		for(int a,b,c,i = 1; i<=m; i++) {
			scanf("%d%d%d",&a,&b,&c);
			e[++tot].u = a;e[tot].v = b;e[tot].w = c;
			init();
			printf("%d\n",klu());
		}
	}


	return 0 ;
}