1014 - 动态维护最小生成树 - Maintain（IOI 2003）

Maintain

描述

农夫约翰的奶牛们希望能够在农场的N(1<=N<=200)块田地中自由的旅游，尽管这些田地被树林分开了。他们希望能够通过维护一对对田地间的路径使得任意两块田地间都有通路。奶牛们可以沿着任一方向的维护的路径旅游。

奶牛们并不建立路径，取而代之，他们维护他们所发现的野生动物建立的路径，任意一周，他们可以选择维护任意的一个或所有的他们所知道的野生动物建立的路径。

令人惊奇的是，奶牛们在每周周初总会发现一条新的野生动物建立的路径。在这之后，他们必须在当周决定需要维护的那套路径使得任意两块田地间都有通路。奶牛们只能维护目前所使用的路径。 　　 奶牛们总是希望减少他们必须维护的路径的总长度。他们可以维护任意的子集，这个子集是他们已知的野生动物的路径，这些路径必须是他们上周维护的或是本周发现的。 　　 野生动物的路径不是直的。连接两点可能有多条路径，他们可能有不同的长度。两条路径可能相交，但奶牛们很牛，除非他们在一块田地里，他们拒绝改变路线。

输入

输入的第一行给出两个正整数N和W，两个数之间用空格分开，W是程序应运行的星期数(1 <= W <= 200)。

对于每个星期，读入一行，这一行包含着当周被发现的野生动物建立的路径，每一行包含着用空格分开的三个整数，路径的两个端点（田地的号码）和该路径的长度（1到10000的整数）。没有任何路径是以某地发出并以该地结束的。

输出

在你的程序了解一条新的野生动物路径后，你需要输出一个数，这个数是奶牛们需要维护的满足题目要求的路径的总长度的最小值。如果没有一套路径能使得奶牛们可以在任意两块田地间通行的话，输出-1。

你的程序应该在完成最后一周的任务后退出。

样例输入

4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2

样例输出

-1
-1
-1
14
12
8

 

简化版题意

 

 

分析

基础训练

插入排序+Kruskal

时间复杂度：由于在加边的同时对边进行插入排序，当边的数量≥n-1时，进行kruskal，此时每次kruscal的复杂度为O（m），算法的时间复杂度为O(m^2)

 

代码

#include<bits/stdc++.h>
using namespace std;
int n,w,len=0,fa[209],bg=0;
bool fg=0;
struct node{int u,v,w;}p,a[2000];
int getfa(int x){
	if(x!=fa[x]) fa[x]=getfa(fa[x]);
	return fa[x];
}
void insert_sort(){
	int i,j;
	for(i=len;i>=1;--i) if(a[i].w<=p.w) break;
	for(j=len;j>i;--j) a[j+1]=a[j];
	a[++i]=p;++len;
}
int ans;
bool kruskal(){
	ans=0;
	int num=0,i;
	for(i=1;i<=n;++i) fa[i]=i;
	for(i=1;i<=len;++i){
		int fu=getfa(a[i].u),fv=getfa(a[i].v);
		if(fu!=fv){
			fa[fu]=fv;ans+=a[i].w;
			bg=a[i].w;++num;
			if(num==n-1) return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&w);
	int i,j,k;
	for(i=1;i<=w;++i){
		scanf("%d%d%d",&p.u,&p.v,&p.w);
		if(fg&&p.w>bg){printf("%d\n",ans);continue;	}
		insert_sort();
		if(!kruskal()){printf("-1\n");		}
		else {
			printf("%d\n",ans);
			fg=1;//图是否已联通
		}
	}
	return 0;
}