jzoj 1751. Span 最小生成樹+枚舉

Description

　　某國有N個村子，M條道路，為了實作“村村通工程”現在要”油漆”N-1條道路（因為某些人總是說該國所有的項目全是從國外進口來的，隻是漆上本國的油漆罷了），因為“和諧”是此國最大的目标和追求，以緻于對于最小造價什麼的都不在乎了，隻希望你所選出來的最長邊與最短邊的差越小越好。

Input

　　第一行給出一個數字TOT，代表有多少組資料,Tot<=6

　　對于每組資料，首先給出N，M

　　下面M行，每行三個數a,b,c代表a村與b的村道路距離為c.

Output

　　輸出最小內插補點,如果無解輸出”-1”.

Sample Input

1

4 5

1 2 3

1 3 5

1 4 6

2 4 6

3 4 7

Sample Output

1

Data Constraint

Hint

【樣例解釋】

　　選擇1-4,2-4,3-4這三條邊.

【資料範圍】

　　1:2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2

　　2:每條邊的權值小于等于10000

　　3:保證沒有自環，沒有重邊

解法：最小生成樹+枚舉

這道題一看就是暴力，n≤100，随便搞搞就A了

1. 因為題目中要求在所有生成樹中讓我們求最大值和最小值內插補點最小，我們可以枚舉每一個生成樹
2. 思考如何更好的求出內插補點？我們可以把所有邊從大到小排一次序，那麼我們求出生成樹之後，我們隻需要将最開始的那條邊的權值減去最後那條的邊的權值和ans取更小值即可，因為我們已經排過序了，是以這樣是正确的
3. 關于最小生成樹，我就不多bb了，但我還是怕有一些跳級生不懂如何求最小生成樹，我在這兒講一下kruscal算法，kruscal算法的輔助算法是并查集
4. 由于一棵樹的邊數為點數減1，是以我們要求出一顆樹的最小生成樹，隻需要将邊權從小到大排好序之後，每次取出一條邊的兩端，如果沒有在一個集合裡，我們就合并在一起，然後把目前邊權加到ans裡即可

AC代碼

#include<cstdio>
#include<algorithm>
#include<cstring>
#define re register int
using namespace std;
struct edge {
	int a,b,w;
}e[20010];
int T,n,m,k,ans,fa[10010];
inline int read() {
	char ch=getchar();
	int x=0,cf=1;
	while(ch<'0'||ch>'9') {
		if(ch=='-') cf=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*cf;
}
inline int min(int A,int B) { return A<B?A:B; }
inline bool cmp(edge A,edge B) { return A.w>B.w; }
inline int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main() {
	T=read(); while(T--) {
		n=read(),m=read(); ans=0x3f3f3f3f;
		for(re i=1;i<=m;i++) {
			e[i].a=read(),e[i].b=read();
			e[i].w=read();
		}
		sort(e+1,e+m+1,cmp);
		for(re i=1;i<=m;i++) {
			for(re j=1;j<=n;j++) fa[j]=j; k=0;
			for(re j=i;j<=m;j++) {
				int x=e[j].a,y=e[j].b;
				if(find(x)!=find(y)) {
					fa[find(x)]=find(y); k++;
					if(k==n-1) {
						ans=min(ans,e[i].w-e[j].w);
						break;
					}
				}
			}
		}
		if(ans==0x3f3f3f3f) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}