| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我的47ms,只用了路径压缩这一个优化In Reply To:我的也63ms^_^ Posted by:nazgul1991 at 2010-04-06 16:07:28 /*Source Code
Problem: 2395 User: fyq
Memory: 488K Time: 47MS
Language: G++ Result: Accepted
*/
#include <cstdio>
#define maxn 3001
#define maxm 15001
using namespace std;
typedef struct node
{
int x,y,cost;
}node;
int fa[maxn+1];
node g[maxm+1];
int n,m;
void qsort(int l,int r)
{
int i = l,j = r;
int m = g[(i+j)/2].cost;
node t;
while (i<=j)
{
while (g[i].cost<m) i++;
while (m<g[j].cost) j--;
if (i<=j)
{
t = g[i]; g[i] = g[j]; g[j] = t;
i++; j--;
}
}
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
int find(int x)
{
int k = x;
while (fa[k]!=-1)
k = fa[k];
int t = x;
int temp;
while (t!=k)
{
temp = fa[t];
fa[t] = k;
t = temp;
}
return k;
}
int kruskal()
{
int ans;
for (int i=1;i<=n;i++)
fa[i] = -1;
int total = 0;
for (int i=1;i<=m;i++)
{
int ancx = find(g[i].x);
int ancy = find(g[i].y);
if (ancx!=ancy)
{
ans = g[i].cost;
fa[ancx] = fa[ancy];
total ++;
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
int a,b,c;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
g[i].x = a; g[i].y = b; g[i].cost = c;
}
qsort(1,m);
printf("%d\n",kruskal());
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator