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) cout << ">>> " << #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; /////////////////////////////////////////////////////////////////////////// const int MAX = 2007; int N, M; int parent[MAX]; int get(int n) { return parent[n] = (n == parent[n] ? n : get(parent[n])); } bool joined(int a, int b) { a = get(a); b = get(b); return a == b; } void join(int a, int b) { a = get(a); b = get(b); parent[a] = b; } struct Edge { int a, b, c; bool operator<(const Edge & e) const { return c < e.c; } } edges[1000000]; vector<pair<int, int> > tree[MAX]; int dist[MAX][MAX]; void go(int root, int node, int parent, int best) { dist[root][node] = best; REP(i, tree[node].size()) { int next = tree[node][i].first, c = tree[node][i].second; if (next != parent) go(root, next, node, max(best, c)); } } int main() { while (scanf("%d%d", &N, &M) == 2) { REP(i, N) { parent[i] = i; tree[i].clear(); } REP(i, M) { scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c); --edges[i].a; --edges[i].b; } sort(edges, edges+M); int used = 0, sum = 0; REP(i, M) if (!joined(edges[i].a, edges[i].b)) { join(edges[i].a, edges[i].b); sum += edges[i].c; ++used; tree[edges[i].a].push_back(make_pair(edges[i].b, edges[i].c)); tree[edges[i].b].push_back(make_pair(edges[i].a, edges[i].c)); } if (used != N-1) { printf("disconnected\n"); continue; } REP(i, N) go(i, i, -1, 0); int result = 1000000000; REP(i, M) { int a = edges[i].a, b = edges[i].b; result = min(result, sum-dist[a][b]-edges[i].c); } printf("%d\n", result); } return 0; }
--- c4.s587.cteam052.spider.cpp.0.spider.cpp +++ c4.s953.cteam052.spider.cpp.0.spider.cpp @@ -57,9 +57,28 @@ } edges[1000000]; +vector<pair<int, int> > tree[MAX]; +int dist[MAX][MAX]; + +void go(int root, int node, int parent, int best) +{ + dist[root][node] = best; + REP(i, tree[node].size()) + { + int next = tree[node][i].first, c = tree[node][i].second; + if (next != parent) + go(root, next, node, max(best, c)); + } +} + int main() { while (scanf("%d%d", &N, &M) == 2) { - REP(i, N) parent[i] = i; + REP(i, N) + { + parent[i] = i; + tree[i].clear(); + } + REP(i, M) { @@ -70,25 +89,28 @@ sort(edges, edges+M); - int used = 0, result = 0; - if (M) - { - result -= edges[M-1].c; - join(edges[M-1].a, edges[M-1].b); - ++used; - } - REP(i, M-1) - { + int used = 0, sum = 0; + REP(i, M) if (!joined(edges[i].a, edges[i].b)) { join(edges[i].a, edges[i].b); - result += edges[i].c; + sum += edges[i].c; ++used; + tree[edges[i].a].push_back(make_pair(edges[i].b, edges[i].c)); + tree[edges[i].b].push_back(make_pair(edges[i].a, edges[i].c)); } - } - if (used != N-1) + { printf("disconnected\n"); - else - printf("%d\n", result); + continue; + } + + REP(i, N) go(i, i, -1, 0); + int result = 1000000000; + REP(i, M) + { + int a = edges[i].a, b = edges[i].b; + result = min(result, sum-dist[a][b]-edges[i].c); + } + printf("%d\n", result); } return 0;