Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; ////////////////////////////////// #define MAXN 1111111 int N, M; //vector<int> graph[MAXN], cost[MAXN]; int eA[MAXN], eB[MAXN], eC[MAXN], e[MAXN]; int father[MAXN], rank[MAXN]; int root(int v){ if(father[v] == -1) return v; return (father[v] = root(father[v])); } int used; int DFU(int edge){ int a = eA[edge], b = eB[edge], c = eC[edge]; int ca = root(a), cb = root(b); //DEBUG(a); DEBUG(b); DEBUG(ca); DEBUG(cb); if(ca == cb) return 0; if(rank[ca] < rank[cb]) father[ca] = cb; else if(rank[ca] > rank[cb]) father[cb] = ca; else{ father[ca] = cb; rank[cb]++; } used++; return c; } bool cmp(int a, int b){ return eC[a] < eC[b]; } int main() { while(scanf("%d%d", &N, &M) != EOF){ int m = 0; REP(i, M){ int a, b, c; scanf("%d%d%d", &a, &b, &c); a--; b--; eA[i] = a; eB[i] = b; eC[i] = c; // graph[a].push_back(b); // graph[b].push_back(a); // cost[a].push_back(c); // cost[b].push_back(c); e[i] = i; if(eC[m] < eC[i]) m = i; } REP(i, N){ father[i] = -1; rank[i] = 0; } eC[m] *= -1; sort(e, e + M, cmp); int sum = 0; used = 0; REP(i, M) sum += DFU(e[i]); //printf("used: %d\n", used); if(used == N-1) printf("%d\n", sum); else printf("disconnected\n"); } return 0; }
--- c4.s1226.cteam002.spider.cpp.0.spider.cpp +++ c4.s1243.cteam002.spider.cpp.0.spider.cpp @@ -44,4 +44,5 @@ int a = eA[edge], b = eB[edge], c = eC[edge]; int ca = root(a), cb = root(b); + //DEBUG(a); DEBUG(b); DEBUG(ca); DEBUG(cb); if(ca == cb) return 0; if(rank[ca] < rank[cb]) father[ca] = cb; @@ -75,7 +76,9 @@ // cost[b].push_back(c); e[i] = i; + if(eC[m] < eC[i]) m = i; + } + REP(i, N){ father[i] = -1; rank[i] = 0; - if(eC[m] < eC[i]) m = i; } eC[m] *= -1; @@ -84,4 +87,5 @@ used = 0; REP(i, M) sum += DFU(e[i]); + //printf("used: %d\n", used); if(used == N-1) printf("%d\n", sum); else printf("disconnected\n");