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

## 真是奇怪，好多人都100ms以内，我的却300多ms，速度慢了三倍

Posted by 15211160230 at 2016-08-23 16:17:57 on Problem 3522
```在网上找了代码，思路几乎一样，代码也差别不大，速度却快好几倍，难道枚举过程中层层函数的调用浪费不少时间？一个功能几乎镶嵌在一个函数中，我的分多个函数，看起来比较容易理解
#include <stdio.h>
#include <limits.h>
#include <algorithm>
#define MAXN 101
using namespace std;
typedef struct
{	int x,y;
int cost;
}Edge;
Edge de[5001];
int parent[MAXN],vexnum,edgenum;
void Initial()
{	for(int i=1;i<=vexnum;++i)
parent[i]=i;
}
bool cmp(Edge i,Edge j)
{	if(i.cost<j.cost)	return true;
return false;
}
int FindRoot(int x)
{	if(x!=parent[x])
parent[x]=FindRoot(parent[x]);
return parent[x];
}
bool Union(int i,int j)
{	int x=FindRoot(i),y=FindRoot(j);
if(x==y)	return false;
parent[x]=y;
return true;
}
int kruskal(int k)
{	int i,len=0,s;
for(i=k;i<edgenum;++i)
if(Union(de[i].x,de[i].y)==true)
len++,s=i;
if(len!=vexnum-1)	return -1;
return de[s].cost-de[k].cost;
}
int SmallestSlimness()
{	int i,j,min=INT_MAX,k;
sort(de,de+edgenum,cmp);
for(i=0;i<edgenum;++i)
{	if(edgenum-i<vexnum-1)
break;
Initial();
if((k=kruskal(i))!=-1&&k<min)
min=k;
}
if(min==INT_MAX)	return -1;
return min;
}
int main()
{	int n,m,i;
while(scanf("%d %d",&n,&m)!=EOF)
{	if(n==0&&m==0)	break;
vexnum=n,edgenum=m;
for(i=0;i<m;++i)
scanf("%d %d %d",&de[i].x,&de[i].y,&de[i].cost);
printf("%d\n",SmallestSlimness());
}
return 0;
}```

Followed by: