Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <climits> #include <cstring> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <vector> #define FOR(I,A,B) for(int I = (A); I < (B); ++I) // #define INF (int)2e9 #define EPS 1e-9 #define PI 3.14159265358979 using namespace std; typedef pair<int, int> ii; typedef long long ll; typedef unsigned long long ull; #define MAXN 2100 #define MAXM 1100000 #define LOGMAXN 50 struct Vrchol{ Vrchol* parent; int rank; }; struct Hrana{ int z, d, cena; bool operator<(const Hrana&h)const{ return cena<h.cena; } }; Vrchol* root(Vrchol*v){ Vrchol* r = v; while(r->parent!=0) r = r->parent; while(v!=r){ Vrchol*n=v->parent; v->parent = r; v = n; } return r; } bool join(Vrchol* a, Vrchol* b){ a=root(a); b=root(b); if(a==b) return false; else{ if(a->rank>b->rank) b->parent=a; else if(a->rank<b->rank) a->parent = b; else b->parent = a, a->rank++; } return true; } int N, M; vector<int> tree[MAXN]; vector<int> ceny[MAXN]; int sum; int nejd; int T[MAXN]; int L[MAXN]; int P[MAXN][LOGMAXN]; int E[MAXN]; int H[MAXN][LOGMAXN]; int X; void dfs(int v, int p, int e, int l) { T[v] = p; L[v] = l; E[v] = e; FOR (i, 0, tree[v].size()) { if (tree[v][i]!=p) dfs(tree[v][i], v, ceny[v][i], l+1); } } void process() { int i, j; for (i=0; i<N; i++) for (j=0; 1<<j<N; j++) { P[i][j] = -1; H[i][j] = 0; } for (i=0; i<N; i++) { P[i][0] = T[i]; H[i][0] = E[i]; } for (j=1; 1<<j < N; j++) for (i=0; i<N; i++) if (P[i][j-1]!=-1) { P[i][j] = P[P[i][j-1]][j-1]; H[i][j] = max(H[i][j-1], H[P[i][j-1]][j-1]); } } int query(int p, int q) { int lo, i; int ret = 0; if (L[p] < L[q]) { swap(p, q); } for (lo=1; 1<<lo <=L[p]; lo++); lo--; for (i=lo; i>=0; i--) if (L[p] - (1<<i) >=L[q]) { ret = H[p][i]; p = P[p][i]; } if (p==q) return ret; for (i=lo; i>=0; i--) if (P[p][i] != -1 && P[p][i] != P[q][i]) { ret = max(ret, H[p][i]); ret = max(ret, H[q][i]); p = P[p][i]; q = P[q][i]; } return max(ret, max(E[p], E[q])); } Hrana hrany[MAXM]; Vrchol vrcholy[MAXN]; bool solve() { X=0; if (scanf("%d%d",&N,&M)<0) return false; for(int i=0;i<N;++i){ vrcholy[i].rank= 0; vrcholy[i].parent= 0; tree[i].clear(); ceny[i].clear(); } for(int i=0;i<M;++i){ scanf("%d%d%d",&hrany[i].z,&hrany[i].d,&hrany[i].cena); hrany[i].z--, hrany[i].d--; } sort(hrany, hrany+M); sum = 0; nejd = 0; for(int i=0;i<M;++i){ if(join(vrcholy+hrany[i].z, vrcholy+hrany[i].d)){ tree[hrany[i].z].push_back(hrany[i].d); ceny[hrany[i].z].push_back(hrany[i].cena); tree[hrany[i].d].push_back(hrany[i].z); ceny[hrany[i].d].push_back(hrany[i].cena); sum+=hrany[i].cena; nejd = max(nejd, hrany[i].cena); X++; } } if (X<N-1) { printf("disconnected\n"); return true; } dfs(0, -1, 0, 0); process(); int ret = INT_MAX; FOR (i, 0, M) { ret = min(ret, sum-query(hrany[i].z, hrany[i].d)-hrany[i].cena); } printf("%d\n", ret); return true; } int main() { while(solve()); return 0; }
--- c4.s1040.cteam014.spider.cpp.0.spider.cpp +++ c4.s1067.cteam014.spider.cpp.0.spider.cpp @@ -29,5 +29,5 @@ #define MAXN 2100 #define MAXM 1100000 -#define LOGMAXN 20 +#define LOGMAXN 50 struct Vrchol{ @@ -145,4 +145,5 @@ vrcholy[i].rank= 0; vrcholy[i].parent= 0; + tree[i].clear(); ceny[i].clear(); } for(int i=0;i<M;++i){