# 114 条题解

• @ 2017-07-04 17:38:31

算法最小生成树，算是模版题,不加优化58毫秒
加优化25s左右

``````#include<bits/stdc++.h>
using namespace std;
const int maxn=1000100;
int n,m;
int fa[maxn];
struct note
{
int s,v,w;
}e[maxn];
bool cmp(note a,note b)
{
return a.w<b.w;
}
int ff(int x)
{
return fa[x]=(fa[x]==x)?x:ff(fa[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>e[i].s>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
int rest=n-1;
int ans1=0,ans2=0;
for(int i=1;i<=m;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
if(!rest) break;
int p1,p2;
p1=ff(e[i].s);
p2=ff(e[i].v);
if(p1==p2) continue;
fa[p1]=p2;
ans1++;
rest--;
ans2=e[i].w;
}
cout<<ans1<<" "<<ans2;
return 0;
}
``````
• @ 2019-02-13 11:06:31

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#define Max 1000100
using namespace std;
int fa[Max];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
{
int u,v,c;
}f[Max];
{
return a.c<b.c;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&f[i].u,&f[i].v,&f[i].c);
}
sort(f+1,f+1+m,cmp);
for(int i=1;i<=m;i++)
{
fa[i]=i;
}
int ans1,ans2;
ans1=0,ans2=0;
int rest;
rest=n-1;
for(int i=1;i<=m;i++)
{
if(!rest)
break;
int x,y;
x=find(f[i].u);
y=find(f[i].v);
if(x==y)
continue;
fa[x]=y;
ans1++;
rest--;
ans2=f[i].c;
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}

• @ 2017-07-04 17:41:09

最小生成树裸题

``````#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct Edge
{
int u,v,c;
}e[maxn];
int n,gary,m,p[maxn],ans;
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool cmp(Edge a,Edge b)
{
return a.c<b.c;
}
void init()
{
for(int i=1;i<=m;i++)
{
}
}
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void work()
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=1;i<=m;i++)
{
if(!gary) break;
int x=find(e[i].u),y=find(e[i].v);
if(x!=y)
{
gary--;
p[x]=y;
ans=max(e[i].c,ans);
}
}
cout<<n-1<<" "<<ans<<endl;
}
int main()
{
init();
work();
}
``````
• @ 2018-05-08 19:53:38

Accepted

# 状态 耗时 内存占用

#1 Accepted 8ms 336.0 KiB
#2 Accepted 2ms 360.0 KiB
#3 Accepted 3ms 384.0 KiB
#4 Accepted 2ms 384.0 KiB
#5 Accepted 2ms 372.0 KiB
#6 Accepted 4ms 256.0 KiB
#7 Accepted 4ms 360.0 KiB
#8 Accepted 6ms 384.0 KiB
#9 Accepted 7ms 480.0 KiB
#10 Accepted 7ms 512.0 KiB
---------------------------------------------------
着毫秒数乱七八糟的，强迫症犯了

• @ 2018-03-08 18:23:12

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define ll long long
using namespace std;

struct node
{
int l;
int r;
int val;
}a[10005];

int f[10005];
int n , m ,ans,maxn;

int cmp(node x,node y)
{
return x.val < y.val;
}

int find(int x)
{
if(f[x]==x)
{
return x;
}
return f[x]=find(f[x]);
}

int Kruskal()
{
for(int i = 1;i <= m;i++)
{
int u = a[i].l;
int v = a[i].r;
int uu = find(u);
int vv = find(v);
if(uu == vv)
{
continue;
}else
{
f[vv] = uu;/*f[uu] = vv;*/
ans++;
maxn = max(maxn,a[i].val);
}
}
}

int main()
{
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
cin >> a[i].l >> a[i].r >> a[i].val;
}
for(int i = 1;i <= n;i++)
{
f[i] = i;
}
sort(a+1,a+1+m,cmp);
Kruskal();
cout << ans << " " << maxn <<endl;
return 0 ;
}

• @ 2017-11-19 11:53:53

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 7;
const int M = 1e3 + 7;
int n, m, cnt, ans, f[M];

template <class T>
x = 0;
static char buf = getchar();
for ( ;!isdigit(buf); buf = getchar());
for ( ;isdigit(buf); buf = getchar())
x = x * 10 + buf - 48;
}

struct edge{
int u, v, w;
}way[N];

bool cmp(const edge &x, const edge &y){
return x.w < y.w;
}

inline void init(){
for (int i = 1; i <= n; i ++)
f[i] = i;
}

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

void kruskal(){
init();
sort(way + 1, way + m + 1, cmp);
for (int i = 1; i <= m; i ++){
int fu = find(way[i].u), fv = find(way[i].v);
if (fu != fv) cnt ++, f[fv] = fu;
if (cnt == n - 1) {
ans = way[i].w; break ;
}
}
}

void work(){
for (int i = 1; i <= m; i ++)
kruskal();
cout << cnt << ' ' << ans << endl;
}

int main(){
work(); return 0;
}

• @ 2017-10-18 20:17:34

没有人发prim的话我来补一个。。给学最小生成树的oier提供个模板。

``````#include<iostream>
#include<cstdio>
using namespace std;
int dis[305][305],mina[305],u[305],n,m,i,x,y,be,j,k,ans,minx,minn,tot;
int main()
{
cin>>n>>m;
minn=0x7fffffff/3;
for(i=0;i<=n;i++)
{
mina[i]=0x7fffffff/3;
for(j=0;j<=n;j++)
{
dis[i][j]=0x7fffffff/3;
}
}
for(i=1;i<=m;i++)
{
cin>>x>>y;
cin>>dis[y][x];
dis[x][y]=dis[y][x];
if(dis[x][y]<minn)
{
minn=dis[x][y];
be=x;
}
}
mina[x]=0;
for(int l=1;l<=n;l++)
{
k=0;
for(i=1;i<=n;i++)
{
if(mina[k]>mina[i] && !u[i])
{
k=i;
}
}
u[k]=1;
for(j=1;j<=n;j++)
{
if(!u[j] && mina[j]>dis[j][k])
{
mina[j]=dis[j][k];
}
}
}
for(int q=1;q<=n;q++)
ans=max(mina[q],ans);
cout<<n-1<<" "<<ans;
return 0;
}
``````
• @ 2017-05-29 12:45:00
``````#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct edge_1
{
int x,y,d;
};

int n,m,cnt,max_d;
vector<int> fa;
vector<edge_1> e;

bool cmp_edge_1(edge_1 x,edge_1 y)
{
return x.d<y.d;
}

int find_fa_1(int x)
{
return ((fa[x]==x)?x:(fa[x]=find_fa_1(fa[x])));
}

int unite_1(int x,int y)
{
if (fa[(fa[y]=find_fa_1(fa[y]))]!=(fa[x]=find_fa_1(fa[x])))
{
fa[fa[y]]=fa[x];
return 1;
}
else
return 0;
}

int main()
{
while (~scanf("%d%d",&n,&m))
{
fa.resize(n+1);
for (int i=1;i<=n;i++)
fa[i]=i;
e.resize(m+1);
for (int i=1;i<=m;i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
e[i].x=x,e[i].y=y,e[i].d=d;
}
sort(e.begin()+1,e.end(),cmp_edge_1);
cnt=max_d=0;
for (int i=1;i<=m&&cnt<n-1;i++)
{
int suc=unite_1(e[i].x,e[i].y);
cnt+=suc;
max_d=max(max_d,e[i].d*suc);
}
printf("%d %d\n",cnt,max_d);
}
}
``````
• @ 2017-05-29 12:45:52

很H2O的题

• @ 2017-04-08 13:29:25
``````#include <bits/stdc++.h>
using namespace std;
int f[305];
struct edge
{
int from,to,len;
bool comp(edge a,edge b){
return a.len<b.len;
}
int getf(int x)
{
return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
int n,m,maxw=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1,j=0;i<=m && j<n-1;i++) {
if(p1!=p2) {
f[p1]=p2;
}
}
printf("%d %d",n-1,maxw);
return 0;
}
``````
• @ 2016-03-20 11:50:46

记录信息
评测状态 Accepted
题目 P1190 繁忙的都市
递交时间 2016-03-20 11:49:59
代码语言 C++
评测机 VijosEx
消耗时间 0 ms
消耗内存 368 KiB
评测时间 2016-03-20 11:50:01
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 364 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 368 KiB, score = 10
Accepted, time = 0 ms, mem = 368 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
using namespace std;

const int MaxN = 300 + 10, MaxM = 10000 + 10;

int N, M, A, B, Max;

struct Node {
bool root;
int parent;
}node[MaxN];

struct Eage {
int To, From, Cost;
bool operator < (const Eage& Element) const {
return Element.Cost > Cost;
}
}E[MaxM];

int getInt() {
int Return = 0;
char Get = getchar();
while(Get >= '0' && Get <= '9') {
Return = Return * 10 + (Get - '0');
Get = getchar();
}
return Return;
}

int Find(int Element) {
int theRoot = Element;
while (!node[theRoot].root)theRoot = node[theRoot].parent;
int parentNode;
int Now = Element;
while (Now != theRoot) {
parentNode = node[Now].parent; node[Now].parent = theRoot; Now = parentNode;
}
return theRoot;
}

void Unite(int rootA, int rootB)
{
if (node[rootA].parent < node[rootB].parent) {
node[rootB].parent += node[rootA].parent;
node[rootA].root = 0;
node[rootA].parent = rootB;
}
else {
node[rootA].parent += node[rootB].parent;
node[rootB].root = 0;
node[rootB].parent = rootA;
}
}

int main() {
N = getInt(); M = getInt();
for(int i = 1; i <= N; ++i) {
node[i].root = 1;
node[i].parent = i;
}
for(int i = 1; i <= M; ++i) {
E[i].From = getInt();
E[i].To = getInt();;
E[i].Cost = getInt();
}
sort(E + 1, E + M + 1);
for(int i = 1, j = N; j > 1; ++i) {
A = Find(E[i].From); B = Find(E[i].To);
if(A != B) {
Unite(A, B);
Max = max(Max, E[i].Cost); --j;
}
}
printf("%d %d", N - 1, Max);
return 0;
}

• @ 2016-01-22 09:15:42

此题似乎并不需要生成树，二分答案即可。
时间复杂度为`O(nlogn)`

``````#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 300

struct Edge {
Edge() : u(0), v(0), w(0) {}
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

int u;
int v;
int w;
};  // struct Edge

typedef vector<Edge *>::iterator iterator_t;

static int n;
static int m;
static int size;
static int set[NMAX + 10];
static vector<Edge *> edges;

bool compare(const Edge *a, const Edge *b) {
return a->w < b->w;
}

inline void make_set() {
size = n;

for (int i = 1; i <= n; i++) {
set[i] = i;
}  // for
}

inline int find_set(int x) {
return x == set[x] ? x : set[x] = find_set(set[x]);
}

inline void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);

if (x != y) {
set[x] = y;
size--;
}
}

void initialize() {
scanf("%d %d", &n, &m);

edges.reserve(m);
int x, y, c;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &c);

if (x == y)
continue;

Edge *p = new Edge(x, y, c);
edges.push_back(p);
}  // for

sort(edges.begin(), edges.end(), compare);
}

void quit() {
printf("%d %d", n - 1, answer);
}

bool test(int limit) {
make_set();

for (iterator_t beg = edges.begin();
beg != edges.end() and (*beg)->w <= limit;
beg++) {
Edge *e = *beg;
union_set(e->u, e->v);
}  // for

return size == 1;
}

int main() {
initialize();

int left = 0, right = edges.size() - 1;
while (right - left > 1) {
int mid = (left + right) >> 1;

bool flag = test(edges[mid]->w);
if (flag) {
right = mid;
} else {
left = mid;
}
}  // while

if (left != right and !test(edges[left]->w)) {
left = right;
}

quit();
return 0;
}  // function main

``````
• @ 2016-11-09 22:58:16

最小生成树的代码长度仅为您这个的1/4啊

• @ 2017-05-04 13:04:40

是啊

• @ 2015-10-07 10:39:08
• @ 2015-10-07 10:25:35

大神们，这一道题能用prim做么？在线等

• @ 2015-10-07 10:25:53

能！

• @ 2015-10-07 10:26:21

为什么？

• @ 2015-10-07 10:27:01

因为

你长得特别丑！

• @ 2015-10-07 10:27:20

你********

• @ 2015-10-07 10:28:13

都懒得骂你

• @ 2015-10-07 10:28:23

sb

• @ 2015-10-07 10:28:36

laji

• @ 2015-10-07 10:28:51

除了会吃时还会干什么？

• @ 2015-08-29 11:27:44

半裸的Krustal
#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn=305;
const int maxm=maxn*maxn/2;
int p[maxn];

struct edge
{
int from,to;
int weight;

bool operator < (const edge& A,const edge& B)
{
return A.weight < B.weight;
}
int getP(int x)
{
return p[x]==x?x:p[x]=getP(p[x]);
}
int main()
{
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++) {
}

int maxW=0;
for(int i=1;i<=N;i++) p[i]=i;
for(int i=0,j=N;j>1;i++) {
if(p1!=p2) {
p[p1]=p2;
j--;
}
}

printf("%d %d",N-1,maxW);
return 0;
}

• @ 2015-08-19 16:34:33

该题显然用n-1条边将每个节点连接。
要求最大权值最小，说明构造的最小生成树最大的边权输出即可。
因为 最小生成树以贪心的方法构造，其中选的边都是可用的中最小的，假如换掉其中一条边，必然使总权值变大，且最大边权要么仍等于最小生成树的最大边权，要么比其大。 因为 若换的为最小生成树中不是最大边权的边，那么最大边权保持不变，否则使得最大边权变大。
由此可以得出最大边权最小必然是最小生成树的最大边权。

由此得出算法 Kruscal算法即可。

###代码如下

program p1190;
type rec=record
s,e,v:longint;
end;
var n,m:longint;
ans,i,j,k:longint;
father:array[1..300] of integer;
map:array[1..90000] of rec;

function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;

procedure qsort(i,j:longint);
var l,r,mid:longint;
temp:rec;
begin
l:=i;
r:=j;
mid:=map[(l+r)>>1].v;
while l<=r do
begin
while map[l].v<mid do inc(l);
while map[r].v>mid do dec(r);
if l<=r
then
begin
temp:=map[l];
map[l]:=map[r];
map[r]:=temp;
inc(l);
dec(r);
end;
end;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

function find(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;

procedure unite(a,b:longint);
begin
father[find(father[a])]:=find(father[b]);
end;
begin
for i:=1 to m do
begin
map[i+m].s:=map[i].e;
map[i+m].e:=map[i].s;
map[i+m].v:=map[i].v;
end;
qsort(1,2*m);
for i:=1 to n do father[i]:=i;
for i:=1 to 2*m do
begin
if find(map[i].s)<>find(map[i].e)
then
begin
unite(map[i].s,map[i].e);
ans:=max(ans,map[i].v);
end;
end;
write(n-1,' ',ans);
end.
###评测结果

测试数据 #0: Accepted, time = 23 ms, mem = 1840 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 1840 KiB, score = 10
Accepted, time = 99 ms, mem = 1844 KiB, score = 100

• @ 2015-03-21 08:47:51

#include<cstdio>
#include<algorithm>

using namespace std;

struct kruskal{
int a,b,value;
};

int n,m,son[1001],father[1001],total=0;
kruskal edge[10000];

bool cmp(const kruskal & a,const kruskal & b){
return a.value<b.value;
}

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

bool join(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return false;
}
else if(son[x]<=son[y]){
father[x]=y;
son[y]+=son[x];
}
else{
father[y]=x;
son[x]+=son[y];
}
return true;
}

int main(){
scanf("%d%d",&n,&m);
for(int j=0;j<k;j++){
sum=0;
total=0;
for(int i=1;i<=n;i++){
father[i]=i;
son[i]=1;
}

for(int i=0;i<m;i++){
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}

sort(edge,edge+m,cmp);

for(int i=0;i<m;i++){
if(join(edge[i].a,edge[i].b)){
total++;
sum+=edge[i].value;
}
if(total==n-1){
printf("%d %d",total edge[i].value);
return 0;
}
}
}

• @ 2014-10-29 16:22:51

优先队列优化的Kruskal+并查集
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
struct Edge
{
int u, v, dis;
bool operator< (const Edge &rhs) const
{
return dis > rhs.dis;
}
};
int n, m, maxs = 0;
priority_queue<Edge> e;
int fa[311];
int FIND(int x)
{
if(fa[x] == x)return x;
else return fa[x] = FIND(fa[x]);
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin >> n >> m;
int tu, tv, tdis;
for(int i = 0; i < m; ++i)
{
cin >> tu >> tv >> tdis;
e.push((Edge){tu, tv, tdis});
}
memset(fa, 0, sizeof(fa));
for(int i = 1; i <= n; ++i)fa[i] = i;
while(!e.empty())
{
Edge cur = e.top();
e.pop();
int a = FIND(cur.u), b = FIND(cur.v);
if(a == b)continue;
fa[a] = b;
maxs = cur.dis;
}
cout << n - 1 << " " << maxs << endl;
return 0;
}

• @ 2014-10-29 16:25:29

不过貌似因为用了STL所以速度很差……是不是我有哪里写错了- -|||
测试数据 #0: Accepted, time = 93 ms, mem = 468 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #3: Accepted, time = 7 ms, mem = 284 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 368 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 372 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 368 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 468 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 472 KiB, score = 10

• @ 2014-10-05 15:33:31

program p1190;
var
sum,max,i,j,min,x,y,z,n,m,k:longint;
a:array[1..1000,1..1000]of longint;
b,c,d:array[1..1000]of longint;
procedure prim;
begin
sum:=0;
for i:=1 to n do begin d[i]:=a[1,i];b[i]:=1;end;
for j:=2 to n do begin
min:=maxlongint;
for i:=1 to n do
if (d[i]<>0)and(d[i]<min) then begin min:=d[i];k:=i;end;
sum:=sum+1;if d[k]>max then max:=d[k];d[k]:=0;
for i:=1 to n do
if (a[k,i]<d[i])and(i<>k) then begin d[i]:=a[k,i];b[i]:=k;end;
end;
end;
begin
for i:=1 to n do for j:=1 to n do a[i,j]:=1000000000;
for i:=1 to n do a[i,i]:=0;
for i:=1 to m do begin
prim;
writeln(sum,' ',max);
end.
秒杀，爽

• @ 2014-10-04 17:04:04

#include<algorithm>
#include<iostream>
using namespace std;
struct q
{
int a,b,c;
}p[100001];
int f[100001];
int c(q a,q b)
{
return a.c<b.c;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
main()
{
int m,n,i,x,y,k=0;
long long s=0,t=0;
cin>>n>>m;
cout<<n-1<<' ';
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
cin>>p[i].a>>p[i].b>>p[i].c;
sort(p+1,p+m+1,c);
for(i=1;i<=m;i++)
{
x=find(p[i].a);
y=find(p[i].b);
if(x!=y)
{
f[x]=y;
s+=p[i].c;
k++;
if(k==n-1)
{
cout<<p[i].c;
return 0;
}
}
}
}

• @ 2014-04-12 10:36:31

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 300;

struct EDGE {
int a;
int b;
int c;
} w[10000];

int n, m;
int p[MAXN + 1];

bool cmp(const EDGE e1, const EDGE e2)
{
return (e1.c < e2.c);
}

int find(int a)
{
int x = p[a];
while (p[x] != x) x = p[x];
return x;
}

void union_set(int a, int b)
{
a = find(a);
b = find(b);
p[b] = a;
}

int Kruskal(int & s, int & l)
{
int i;
for (i = 1; i <= n; ++i) p[i] = i;

s = l = 0;
for (i = 1; i <= m; ++i) {
if (find(w[i].a) != find(w[i].b)) {
union_set(w[i].a, w[i].b);
++s;
if (w[i].c > l) l = w[i].c;
}
}
return 0;
}

int main()
{
cin >> n >> m;

int i;
for (i = 1; i <= m; ++i) cin >> w[i].a >> w[i].b >> w[i].c;

sort(&w[1], &w[m + 1], cmp);

int s, l;
Kruskal(s, l);

cout << s << " " << l;

return 0;
}

ID
1190

5

2962

1132

38%

7