当前位置:首页 > 开发 > 移动开发 > 正文

POJ 2421 Constructing Roads 最小生成树

发表于: 2012-08-18   作者:aijuans   来源:转载   浏览:
摘要: 来源:http://poj.org/problem?id=2421 题意:还是给你n个点,然后求最小生成树。特殊之处在于有一些点之间已经连上了边。 思路:对于已经有边的点,特殊标记一下,加边的时候把这些边的权值赋值为0即可。这样就可以既保证这些边一定存在,又保证了所求的结果正确。 代码: #include <iostream> #include <cstdio>

来源:http://poj.org/problem?id=2421

题意:还是给你n个点,然后求最小生成树。特殊之处在于有一些点之间已经连上了边。

思路:对于已经有边的点,特殊标记一下,加边的时候把这些边的权值赋值为0即可。这样就可以既保证这些边一定存在,又保证了所求的结果正确。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <climits>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 110;
int father[N];
struct edge{
	int lp,rp,value;
}ee[N*N];
int map[N][N],flag[N][N],numedge,n;
bool cmp(edge a,edge b){
	return a.value < b.value;
}
int find(int x){
	if(x == father[x])
		return father[x];
	return find(father[x]);
}
bool Union_Set(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx == fy){
	  return false;
	}
	else{
	  father[fx] = fy;
	  return true;
	}
}
int kruskal(){
	sort(ee,ee+numedge,cmp);
	for(int i = 1; i <= n; ++i)
		father[i] = i;
	int sum = 0;
	for(int i = 0; i < numedge; ++i){
		int lx = ee[i].lp;
		int rx = ee[i].rp;
		if(Union_Set(lx,rx)){
			sum += ee[i].value;
		}
	}
	return sum;
}
int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%d",&n) != EOF){
      CLR(flag,0);
		for(int i = 1; i <= n; ++i){
		  for(int j = 1; j <= n; ++j)
			  scanf("%d",&map[i][j]);
		}
        int m,x,y;
		scanf("%d",&m);
		while(m--){
		  scanf("%d%d",&x,&y);
		  flag[x][y] = 1;
		}
		numedge = 0;
		for(int i = 1; i < n; ++i){
			for(int j = i + 1; j <= n; ++j){
				if(flag[i][j]){
					ee[numedge].lp = i;
					ee[numedge].rp = j;
					ee[numedge].value = 0;
					numedge++;
				}
				else{
					ee[numedge].lp = i;
					ee[numedge].rp = j;
					ee[numedge].value = map[i][j];
					numedge++;
				}
			}
		}
		int ans = kruskal();
		printf("%d\n",ans);
	}
	return 0;
}


更多详细信息请查看 java教程网 http://www.itchm.com/forum-59-1.html

POJ 2421 Constructing Roads 最小生成树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目 The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid
Jungle Roads Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 19454 Accepted: 8919
Jungle Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Jungle Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Jungle Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Jungle Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Agri-Net Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 37131 Accepted: 14998 Des
Slim Span Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 5412 Accepted: 2842 Desc
一.Prim 算法 int cost[MXV][MXV]; int mincost[MXV]; bool used[MXV]; int V; int prim(){ for(int
简介 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号