原題

1.題意分析

題意就是給你很多組數，對於每組數，有三組小數據。第一組小數據先輸入一個n表示頂點數，然後再輸入n-1條邊表示初始邊數。其它組小數據先輸入一個數k，表示增加的邊的數量，然後再輸入k條邊，表示增加的邊。在輸入第二組小數據時，要先把邊清空，重新輸入，但是邊的數量不變。

2.做法

題意不難理解，說白了就是最小生成樹的板子題。很明顯，對於每組數，可以分為兩組大數據。第一組小數據是一組大數據；第二組和第三組小數據可以分為一組大數據。對於每組大數據，求出最小生成樹，再把數據清空，再求一遍。就是最終的正解了

3.關於最小生成樹

板子

板子題原題

kruskal最小生成樹演算法的詳細分析

註意輸入的換行，換行卡了我10分鐘

它終於來了

代碼

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 100;

int parents[N];

struct edge
{
	int from, to, val;
}edges[N];

bool cmp(edge a, edge b)
{
	if(a.val != b.val)
	{
		return a.val < b.val;
	}else
	{
		return a.from > b.from;
	}
	return a.to > b.to;
}

int cnt = 0;
void add(int u, int v, int w)
{
	cnt++;
	edges[cnt].from = u;
	edges[cnt].to = v;
	edges[cnt].val = w;
}

int Find(int n)
{
	int last_find = n;
	while(true)
	{
		if(parents[n] == n || parents[n] == last_find)
		{
			return n;
		}
		last_find = n;
		n = parents[n];
	}
}

int kruskal(edge* edges, int points, int bian)
{
	int w = 0;
	int cur_cnt = 0;
	int ans = 0;
	sort(edges + 1, edges + bian + 1, cmp);
	while(cur_cnt < points-1)
	{
		w++;
		int node_1 = Find(edges[w].from);
		int node_2 = Find(edges[w].to);
		if(node_1 != node_2)
		{
			parents[Find(node_1)] = parents[Find(node_2)];
			ans += edges[w].val;
			cur_cnt++;
		}
//		cout << cur_cnt << " " << w << endl;
//		cout << ans << endl;
	}
	return ans;
}

void init(int n)
{
	cnt = 0;
	for(int i = 1;i <= n;i++)
	{
		parents[i] = i;
	}
}

int main()
{
	int ccnntt=0;
	int n;
	while(cin >> n)
	{
		if(ccnntt!=0){
			cout<<endl;
		}
		ccnntt++;
		init(n);
		for(int i = 1;i < n;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << kruskal(edges, n, n - 1) << endl;
		
		init(n);
		int k;
		cin >> k;
		for(int i = 1;i <= k;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		int m;
		cin >> m;
		for(int i = 1;i <= m;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << kruskal(edges, n, k + m) << endl;
	}
	
	return 0;	
}