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

prim水过,顺便提醒一下

Posted by pheonix2012 at 2012-12-08 18:02:50 on Problem 1789
#include<iostream>
using namespace std;
#define INF 999;
int dis[2010][2010],lowcost[2010],n;
bool visit[2010];
char type[2010][10];
int transform(int pos,int cmp)
{
	int i,ans=0;
	for(i=0;i<7;i++)
		if(type[pos][i]!=type[cmp][i])
			ans++;
	return ans;
}
int prim()
{
	int i,j,k,temp,flag=0,ans=0;
	for(i=2;i<=n;i++)
		lowcost[i]=dis[1][i];
	for(i=1;i<n;i++)
	{
		temp=1000;
		for(j=2;j<=n;j++)
			if(temp>lowcost[j]&&!visit[j])
				{
					temp=lowcost[j];
					flag=j;
			    }
		visit[flag]=true;
		for(k=1;k<=n;k++)
				if(lowcost[k]>dis[flag][k]&&!visit[k])
					lowcost[k]=dis[flag][k];
		ans+=lowcost[flag];
	}
	return ans;
}
int main()
{
	int i,j;
	while(cin>>n&&n)
	{
		memset(visit,false,sizeof(visit));
		for(i=1;i<2010;i++)
			for(j=1;j<2010;j++)
				dis[i][j]=INF;
		for(i=1;i<=n;i++)
		{
			cin>>type[i];
			for(j=1;j<=i;j++)
				dis[i][j]=dis[j][i]=transform(i,j);
		}
		cout<<"The highest possible quality is 1/"<<prim()<<"."<<endl;
	}
	return 0;
}
哥的结尾句号没输出WA了一次,shit!

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