点击打开链接poj 258
思路:最小生成树 + prime
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
#define INF 0XFFFFFFF
int n;
int vis[MAXN];
int lowcost[MAXN];
int G[MAXN][MAXN];
void init(){
memset(vis , 0 , sizeof(vis));
memset(lowcost , 0 , sizeof(lowcost));
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
G[i][j] = INF;
}
}
void prime(){
int pos , ans;
ans = 0;
vis[1] = 1;
for(int i = 1 ; i <= n ; i++)
lowcost[i] = G[1][i];
for(int i = 1 ; i <= n ; i++){
pos = -1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && (pos == -1 || lowcost[j] < lowcost[pos]))
pos = j;
}
if(pos == -1)
break;
ans += lowcost[pos];
vis[pos] = 1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && lowcost[j] > G[j][pos])
lowcost[j] = G[j][pos];
}
}
printf("%d\n" , ans);
}
int main(){
int tmp;
while(scanf("%d" , &n) != EOF){
init();
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
scanf("%d" , &tmp);
if(G[i][j] > tmp)
G[i][j] = tmp;
}
}
prime();
}
return 0;
}
分享到:
相关推荐
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
POJ水题集-----50道左右-----增加自信啊..
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ初级题-数据结构:解题报告+AC代码
POJ3259--Wormholes,使用bellman方法。
poj题目分类--acmer做题极有用资源
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
poj 2827 Auto-Calculation Machine.md
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
用Java代码实现POJ(PKU)上题2494!
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
1390--blocks.rar