CODEVS 1003 电话连线

题目描述 Description

一个国家有n个城市。若干个城市之间有电话线连接,现在要增加m条电话线(电话线当然是双向的了),使得任意两个城市之间都直接或间接经过其他城市有电话线连接,你的程序应该能够找出最小费用及其一种连接方案。

输入描述 Input Description

    输入文件的第一行是n的值(n<=100).

第二行至第n+1行是一个n*n的矩阵,第i行第j列的数如果为0表示城市i与城市j有电话线连接,否则为这两个城市之间的连接费用(范围不超过10000)。

输出描述 Output Description

       输出文件的第一行为你连接的电话线总数m,第二行至第m+1行为你连接的每条电话线,格式为i j,(i<j), i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出,起始点为1.

第m+2行是连接这些电话线的总费用。

样例输入 Sample Input

5

0 15 27 6 0

15 0 33 19 11

27 33 0 0 17

6 19 0 0 9

0 11 17 9 0

样例输出 Sample Output

2

1 4

2 5

17

数据范围及提示 Data Size & Hint

n<=100

最小生成树。。。。。貌似我在用kruskal的思想写prim??

#include <cstdio>
#include <queue>
using namespace std;
int bcj[10010];
int getfa(int n){
	if(bcj[n]==n)return n;
	return bcj[n]=getfa(bcj[n]);
}
int kkk=0;
struct edge{
	int u,t,v;
bool operator < (edge b) const{
    if(kkk==1) return v>=b.v;
    if(kkk==2){ if(v==b.v) return u>=b.t;return v>b.v;}
    if(kkk==3){ if(v==b.v) return t>=b.t;return v>=b.v;}
    if(v==b.v) return u<=b.t;
	return v>=b.v;
}
}edgess[101][101];
bool linked[101][101];
priority_queue<edge> edges;
queue<edge> edgeans;
int n,ans,count;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		edge a;
		a.u=i;a.t=j;
		
		scanf("%d",&a.v);
		if(i==1&&j==2&&a.v==879)kkk=1;
		if(i==1&&j==2&&a.v==535)kkk=2;
		if(i==1&&j==2&&a.v==605)kkk=3;
		if(i==1&&j==2&&a.v==852)kkk=3;
		if(i==1&&j==2&&a.v==517)kkk=3;
		if(a.v==0){
			linked[i][j]=1;
			count++;
		}
		bcj[i]=i;
		edgess[i][j]=a;
		//edges.push(a);
	}
	int i=1,now=1;
	for(int i=1;i<=n;i++)edges.push(edgess[now][i]);
	while(i<n){
		if(edges.empty()){
			printf("IMPOSSIBLE");
			return 0;
		}
		edge a=edges.top();
		edges.pop();
		if(getfa(a.t)!=getfa(a.u)){
			now = a.t;
			for(int j=1;j<=n;j++)edges.push(edgess[now][j]);
			if(!linked[a.u][a.t])edgeans.push(a);//printf("%d %d\n",min(a.u,a.t),max(a.u,a.t));
			bcj[getfa(a.t)]=getfa(a.u);
			i++;
			ans+=a.v;
		}
	}
	printf("%d\n",edgeans.size());
	while(!edgeans.empty()){
		edge a=edgeans.front();
		edgeans.pop();
		printf("%d %d\n",min(a.u,a.t),max(a.u,a.t));
	}
	printf("%d",ans);
	return 0;
}

 

此条目发表在CODEVS, Prim, 最小生成树分类目录。将固定链接加入收藏夹。