一个无向图、最小生成树的问题…

题目是在一个国家里建路的问题。
一个国家里有N座城市，这些城市之间本身存在着互相连接着的旧路，长度都不一样。
某一些城市和另一些城市之间完全没有旧路，所以这两堆城市互相为两个区域。
现在国家要修建新路，新路只能在旧路的基础上修建，并使得原来互相连接的城市之间距离最短。
一个输入例子：
城市数：10
旧路数：12
路的描述：（城市1 城市2 路的长度）
7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24

输出结果为：
区域一：
8 9 1
7 9 2
区域二：
0 5 10
2 3 12
1 6 14
1 2 16
3 4 22
4 5 25

输出结果要求包含城市数目越小的区域排在越前面。（区域一城市数<区域二城市数）
各个路以长度从小到大排列。
（如果两条路等长，则认为，左城市较小的那个小。如果左城市编号一样，那么右城市小的那个小）

现在我卡了好久卡在不知道如何分区域及排序（不会分区域也没法排序啊QAQ），使用kruskal算法倒是可以得出包含有N个最小生成子树的树林。

求各位大神指教。orz

6 个解决方案

#1

关于分区域首先想到的是：
可以看做一开始有旧路数个集合，比如{7,8}，{7,9}……然后求集合的并集，这样应该是可以区分两个区域的。不过感觉挺麻烦。
或者一开始就当做一个图，存储完后，顺便选一个节点开始遍历，存储遍历到的城市标号，遍历完一遍后收集的就是一个区域的所有城市了吧。
关于排序：
两个区域不用说。
路线的排序可以这么看：每一条线路的值=线路长*100+左城市*10+右城市。排序输出。

供参考。抛砖引玉。

#2

这个还是很好判定的啊

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define N 1000

struct edge
{
	int  a,b,d;
};

bool cmp(const edge &a,const edge &b)
{
	return a.d<b.d;
}

int n,m,father[N],root[N];
edge p[10000];
vector<edge> v;

void init()
{
	memset(father,-1,sizeof(father));
}

int find(int x)
{
	while(father[x]!=-1)
		x=father[x];
	return x;
}

int main()
{
	while(scanf("%d%d",&n,&m)==2)	//n为城市数，m为旧路数
	{
		for(int i=0;i<m;i++)
			scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].d);
		sort(p,p+m,cmp);
		init();
		v.clear();
		int cnt=0;
		for(int i=0;i<m;i++)
		{
			int f1=find(p[i].a),f2=find(p[i].b);
			if(f1==f2)
				continue;
			father[f2]=f1;
			v.push_back(p[i]);
			++cnt;
			if(cnt==n-2)
				break;
		}
		for(int i=0;i<n;i++)
			root[i]=find(i);
		int t1=root[0],cnt1=1,t2=-1,cnt2=0,r;
		for(int i=1;i<n;i++)
		{
			if(root[i]==t1)
				++cnt1;
			else
			{
				t2=root[i];
				++cnt2;
			}
		}
		if(cnt1<=cnt2)
			r=t1;
		else
			r=t2;
		printf("区域一：\n");
		for(int i=0;i<v.size();i++)
		{
			if(root[v[i].a]==r)
				printf("%d %d %d\n",v[i].a,v[i].b,v[i].d);
		}
		printf("区域二：\n");
		for(int i=0;i<v.size();i++)
		{
			if(root[v[i].a]!=r)
				printf("%d %d %d\n",v[i].a,v[i].b,v[i].d);
		}
	}
}

#3

感谢回答。
不过楼上的程序只能分两个区域…事实上一个城市里到底有多少区域是不知道的（最少一个，最多就是每个城市独立为一个区域）
测试例子：
12
12
0 1 1
0 3 1
1 3 1
2 5 1
4 10 1
4 8 1
10 8 1
11 6 2
11 7 2
6 7 1
9 6 1
9 7 1
比如这个测试例子有四个区域…

还有我想知道能否不用STL来做解决这个问题…
非常感谢。

#4

一样能做到，你最好贴完整的题目，而不是你大致的描述

#5

1.处理区域很多方法都可以，我的写起来相对较方便的写法。（没有按照那xml格式输出)
2.To avoid non-determinism of your algorithm when two roads e1=(s1, t1) and e2=(s2, t2) have the same length, consider e1 to be shorter than e2 if and only if
 •min(s1, t1) < min(s2, t2), or
 •min(s1, t1) == min(s2, t2) and max(s1, t1) < max(s2, t2)
 应该是我处理的那种，不是如果(两条路等长，则认为，左城市较小的那个小。如果左城市编号一样，那么右城市小的那个小)
3.Note: If we suspect this to be the case, you will ....
4.对楼主学习经历表示下羡慕嫉妒恨。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 1000	//最大城市数
#define M 10000	//最大旧路数

typedef struct _edge
{
	int  a,b,d;
}edge;

typedef struct _region
{
	int root;
	int minS;
	int cnt;
}region;

bool cmp(const edge &a,const edge &b)
{
	return a.d<b.d;
}

int cmp1(const void *a,const void *b)
{
	edge *aa=(edge*)a,*bb=(edge*)b;
	int min1=aa->a<aa->b?aa->a:aa->b;
	int max1=aa->a<aa->b?aa->b:aa->a;
	int min2=bb->a<bb->b?bb->a:bb->b;
	int max2=bb->a<bb->b?bb->b:bb->a;
	if(aa->d==bb->d)
	{
		if(min1==min2)
			return max1-max2;
		return min1-min2;
	}
	return aa->d-bb->d;
}

int cmp2(const void *a,const void *b)
{
	region *aa=(region*)a,*bb=(region*)b;
	if(aa->cnt==bb->cnt)
		return aa->minS-bb->minS;
	return aa->cnt-bb->cnt;
}

int n,m,father[N],root[N];
edge p[M],v[M];
region reg[N];
int top,cnt,i,j;

void init()
{
	cnt=0;
	top=0;
	for(i=0;i<n;i++)
	{
		father[i]=-1;
		reg[i].cnt=0;
		reg[i].root=i;
	}
}

int find(int x)
{
	while(father[x]!=-1)
		x=father[x];
	return x;
}

int main()
{
	while(scanf("%d%d",&n,&m)==2)	//n为城市数，m为旧路数
	{
		for(i=0;i<m;i++)
			scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].d);
//		sort(p,p+m,cmp);
		qsort(p,m,sizeof(edge),cmp1);
		init();
		for(i=0;i<m;i++)
		{
			int f1=find(p[i].a),f2=find(p[i].b);
			if(f1==f2)
				continue;
			father[f2]=f1;
			v[top++]=p[i];
		}
		for(i=0;i<n;i++)
		{
			root[i]=find(i);
			if(reg[root[i]].cnt==0)
				reg[root[i]].minS=i;
			++reg[root[i]].cnt;
		}
		qsort(reg,n,sizeof(region),cmp2);
		for(i=0;i<n;i++)
		{
			if(reg[i].cnt==0)
				continue;
			printf("区域%d:\n",++cnt);
			for(j=0;j<top;j++)
			{
				if(root[v[j].a]==reg[i].root)
					printf("%d %d %d\n",v[j].a,v[j].b,v[j].d);
			}
		}
	}
}

#6

上面有段没删，重新发下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 1000	//最大城市数
#define M 10000	//最大旧路数

typedef struct _edge
{
	int  a,b,d;
}edge;

typedef struct _region
{
	int root;
	int minS;
	int cnt;
}region;

int cmp1(const void *a,const void *b)
{
	edge *aa=(edge*)a,*bb=(edge*)b;
	int min1=aa->a<aa->b?aa->a:aa->b;
	int max1=aa->a<aa->b?aa->b:aa->a;
	int min2=bb->a<bb->b?bb->a:bb->b;
	int max2=bb->a<bb->b?bb->b:bb->a;
	if(aa->d==bb->d)
	{
		if(min1==min2)
			return max1-max2;
		return min1-min2;
	}
	return aa->d-bb->d;
}

int cmp2(const void *a,const void *b)
{
	region *aa=(region*)a,*bb=(region*)b;
	if(aa->cnt==bb->cnt)
		return aa->minS-bb->minS;
	return aa->cnt-bb->cnt;
}

int n,m,father[N],root[N];
edge p[M],v[M];
region reg[N];
int top,cnt,i,j;

void init()
{
	cnt=0;
	top=0;
	for(i=0;i<n;i++)
	{
		father[i]=-1;
		reg[i].cnt=0;
		reg[i].root=i;
	}
}

int find(int x)
{
	while(father[x]!=-1)
		x=father[x];
	return x;
}

int main()
{
	while(scanf("%d%d",&n,&m)==2)	//n为城市数，m为旧路数
	{
		for(i=0;i<m;i++)
			scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].d);
//		sort(p,p+m,cmp);
		qsort(p,m,sizeof(edge),cmp1);
		init();
		for(i=0;i<m;i++)
		{
			int f1=find(p[i].a),f2=find(p[i].b);
			if(f1==f2)
				continue;
			father[f2]=f1;
			v[top++]=p[i];
		}
		for(i=0;i<n;i++)
		{
			root[i]=find(i);
			if(reg[root[i]].cnt==0)
				reg[root[i]].minS=i;
			++reg[root[i]].cnt;
		}
		qsort(reg,n,sizeof(region),cmp2);
		for(i=0;i<n;i++)
		{
			if(reg[i].cnt==0)
				continue;
			printf("区域%d:\n",++cnt);
			for(j=0;j<top;j++)
			{
				if(root[v[j].a]==reg[i].root)
					printf("%d %d %d\n",v[j].a,v[j].b,v[j].d);
			}
		}
	}
}