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