|
|
back to boardWA6 Posted by SProf 16 Feb 2016 17:19 i try to solve it with kruskal and it gives me wa6 can anyone help me? Re: WA6 Posted by c_pp 11 Jan 2017 01:38 struct edge { int len; int a; int b; }; int rank[1024]; int parent[1024]; edge e[15008]; int n,m; int get_parent(int x) { if (x != parent[x])parent[x] = get_parent(parent[x]); return parent[x]; } bool join_dsu(int x, int y){ x = get_parent(x); y = get_parent(y); if (x == y) return false; if (rank[x] < rank[y]) parent[x] = y; else if (rank[x] > rank[y]) parent[y] = x; else parent[y] = x, ++rank[x]; return true; } // read edges // sort edges by len // p[i] = i, for i = 1..n // let l_min = 0; // i = 1..m // if ( join_dsu( e[i].a, e[i].b) ){ l_min = e[i].len; } // print l_min and all edges where len <= l_min, GOOD LUCK !! |
|
|