Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

貌似写得不是很好

Posted by 894212550 at 2013-05-16 15:06:19 on Problem 1251
#include "iostream"
#include "algorithm"
using namespace std;

int low_point[27];
int map[30][30];
int old_p[27];
int num;

void init(){
	int i,j;
	for(i=0;i<27;i++) low_point[i]=-1;
	for(i=0;i<27;i++) old_p[i]=0;
	for(i=0;i<30;i++)
		for(j=0;j<30;j++)
			map[i][j]=-1;
}

int prim(){
	int v1,v2;
	int n=1;
	int min,cost=0;
	int i,j,k;
	low_point[1]=1;
	old_p[1]=1;
	for(i=1;i<num;i++){
		min=101;
		v2=0;
		v1=0;
		for(j=1;j<=n;j++){
			for(k=1;k<27;k++){
				if(map[low_point[j]][k]>-1 && min>map[low_point[j]][k] && !old_p[k]){
					min=map[low_point[j]][k];
					v2=k;
					v1=low_point[j];
				}
			}
		}
		cost+=min;
		low_point[++n]=v2;
		old_p[v2]=1;
	}
	return cost;
}

int main(){
	cin>>num;
	int i,m,n1;
	char c,c1;
	int n;
	while(num){
		init();
		n1=num;
		while(--n1){
			cin>>c>>n;
			for(i=1;i<=n;i++)
			{
				cin>>c1>>m;
				map[c-'A'+1][c1-'A'+1]=m;
				map[c1-'A'+1][c-'A'+1]=m;
			}
		}
		cout<<prim()<<endl;
		cin>>num;
	}
	return 0;
}
/*
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0


216
30

*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator