Poj 1861 Network (模版kruskal)
题目描述：
Andrew 是某个公司的系统管理员，他计划为他的公司搭建一个新的网络。在新的网络中，有
N 个集线器，集线器之间可以通过网线连接。由于公司职员需要通过集线器访问整个网络，因此
每个集线器必须能通过网线连往其他每个集线器（可以通过其他中间集线器来连接）。
由于有不同长度的网线可供选择，而且网线越短越便宜，因此Andres 所设计的方案必须确保
最长的单根网线的长度在所有方案中是最小的。并不是所有集线器之间都可以直接连接，但
Andrew 会向你提供集线器之间所有可能的连接。
你的任务是帮助Andrew 设计一个网络，连接所有的集线器并满足前面的条件。
输入描述：
输入文件中包含多个测试数据。每个测试数据的第1 行为两个整数：N 和M，N 表示网络中
集线器的数目，2≤N≤1000，集线器的编号从1～N；M 表示集线器之间连接的数目，1≤M≤
15000。接下来M 行描述了M 对连接的信息，每对连接的格式为：所连接的两个集线器的编号，
连接这两个集线器所需网线的长度，长度为不超过106 的正整数。两个集线器之间至多有一对连
接；每个集线器都不能与自己连接。测试数据保证网络是连通的。
测试数据一直到文件尾。
输出描述：
对输入文件中的每个测试数据，首先输出连接方案中最长的单根网线的长度（你必须使得这
个值取到最小）；然后输出你的设计方案：先输出一个整数P，代表所使用的网线数目；然后输出
P 对顶点，表示每根网线所连接的集线器编号，整数之间用空格或换行符隔开。
样例输入：
5 8
1 2 5
1 4 2
1 5 1
2 3 6
2 4 3
3 4 5
3 5 4
4 5 6
样例输出：
4
4
1 5
1 4
2 4
3 5
模版kuskal题，纪念我图论起步中..........
[cpp]
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 10500
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
int par[MAX],n,m,maxedge,cnt;
struct Edge
{
int s,e;
int value;
}edge[MAX],index[MAX];
bool cmp(Edge a, Edge b)
{
return a.value < b.value;
}
int find(int x)//查
{
while(par[x] != x)
x = par[x];
return x;
}
void connect(int a,int b)//并
{
if(a < b)
{
par[b] = a;
}
else
{
par[a] = b;
}
}
void kruskal()
{
int i,j;
maxedge = 0;
cnt = 0;
for(i=1; i<=m; i++)
{
int a = find(edge[i].s);
int b = find(edge[i].e);
if(a != b)
{
connect(a,b);
if(maxedge < edge[i].value);
maxedge = edge[i].value;
cnt ++;
index[cnt].s = edge[i].s;
index[cnt].e = edge[i].e;
}
if(cnt >= n-1)
break;
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m) != EOF)
{
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].value);
}
sort(edge+1,edge+1+m,cmp);
for(i=1; i<=n; i++)
{
par[i] = i;
}
memset(index,0,sizeof(index));
kruskal();
printf("%d\n%d\n",maxedge,cnt);
for(i=1; i<=cnt; i++)
{
printf("%d %d\n",index[i].s,index[i].e);
}
}
return 0;
}
补充：软件开发 , C++ ,
