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

贴一下AC代码

Posted by 15211160230 at 2016-08-21 12:57:36 on Problem 1679
由于记录生成树边的pre数组是全局范围内的,每次调用prim就会修改pre数组,导致WA,花了不少时间找出来的,以后还是注意一下。我的才32ms,好多人都是16ms,可能还有优化的地方把。
#include <stdio.h>
#include <limits.h>
#define MAXN 101
int G[MAXN][MAXN],vexnum; 
int dis[MAXN],visited[MAXN],pre[MAXN];
void Initial(int N)
{	int i,j;
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			G[i][j]=G[j][i]=INT_MAX;
	vexnum=N;
}
int FindMin()
{	int i,k=-1,min=INT_MAX;
	for(i=1;i<=vexnum;++i)
	{	if(visited[i]==1)	continue;
		if(dis[i]<min)		min=dis[i],k=i;
	}
	return k;
}
int Prim(int k)
{	int i,j,lowcost=0;
	for(i=1;i<=vexnum;++i)
	{	dis[i]=G[k][i],visited[i]=0;
		if(dis[i]!=INT_MAX)		pre[i]=k;
	}
	dis[k]=0,visited[k]=1,pre[k]=k;
	for(i=1;i<vexnum;++i)
	{	k=FindMin();
		if(k==-1)	return -1;
		visited[k]=1;
		lowcost+=dis[k];
		for(j=1;j<=vexnum;++j)
		{	if(visited[j]==1||G[k][j]==INT_MAX)		continue;
 			if(dis[j]>G[k][j])	dis[j]=G[k][j],pre[j]=k;
		}
	}
	return lowcost;
}
bool JudgeUnique(int ans)
{	int i,k,res;
	int dispre[MAXN];
	if(vexnum==1)				return true;
	for(i=1;i<=vexnum;++i)		dispre[i]=pre[i];
	for(i=1;i<=vexnum;++i)	
	{	if(dispre[i]==i)		continue;
		k=G[i][dispre[i]];
		G[i][dispre[i]]=G[dispre[i]][i]=INT_MAX;
		res=Prim(1);
		G[i][dispre[i]]=G[dispre[i]][i]=k;
		if(res==ans)			return false;	
	}
	return true;
}
int main()
{	int t,n,m;
	int x,y,w;
	int ans;
	scanf("%d",&t);
	while(t--)
	{	scanf("%d %d",&n,&m);
		Initial(n);
		while(m--)
		{	scanf("%d %d %d",&x,&y,&w);
			if(G[x][y]>w)	G[x][y]=G[y][x]=w;	
		}
		ans=Prim(1);
		if(JudgeUnique(ans)==true)	printf("%d\n",ans);
		else						puts("Not Unique!");
	}
	return 0;
}

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