SCOI2005 繁忙的都市

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2005 繁忙的都市

Date: Thu Sep 06 00:53:34 CST 2018

In Category: NoCategory

Description：

一个图中选出几条道路，使得图联通，边尽可能少，最大边权最小。

$1\le n \le 300,1\le m \le 10000$

Solution：

第三个条件就是 $kruskal$ 中最后被加入的边。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 310

#define MAXM 50010

struct edge

{

	int u,v,w;

}e[MAXM];

bool cmp(edge a,edge b){return a.w < b.w;}

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

	sort(e + 1,e + 1 + m,cmp);

	int ans;

	for(int i = 1;i <= m;++i)

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		f[p] = q;

		ans = e[i].w;

	}

	cout << n - 1 << " " << ans << endl;

	return 0;

}

In tag: 图论-kruskal

wjh15101051