Go to diff to previous submission
#include <vector> #include <algorithm> #include <queue> #include <cstdio> using namespace std; struct edge { int x, y, w; edge() {} edge(int x, int y, int w) : x(x), y(y), w(w) {} bool operator < (const edge &e) const { return w < e.w; } }; vector<int> parent; void init(int n) { parent.resize(n); for (int i = 0; i < n; ++i) { parent[i] = i; } } int find(int i) { if (parent[i] == i) return i; parent[i] = find(parent[i]); return parent[i]; } void merge(int i, int j) { parent[find(i)] = find(j); } bool kruskal(vector<edge> &g, vector<edge> &tree, int n) { init(n); sort(g.begin(), g.end()); edge e = g.back(); tree.push_back(e); merge(e.x, e.y); for(int i = 0; i < (int) g.size(); ++i) { if (find(g[i].x) != find(g[i].y)) { merge(g[i].x, g[i].y); tree.push_back(g[i]); } } return (int) tree.size() == n - 1; } int bfs(vector<vector<pair<int, int> > > &t, int u, int v) { vector<bool> mark(t.size(), false); queue<pair<int, int> > q; q.push(make_pair(u, 0)); mark[u] = true; while(not q.empty()) { int x = q.front().first; int l = q.front().second; q.pop(); //printf("%d %d\n", x, l); fflush(stdout); if (x == v) return l; for (int i = 0; i < (int) t[x].size(); ++i) { int y = t[x][i].first; if (not mark[y]) { mark[y] = true; int nl = max(l, t[x][i].second); q.push(make_pair(y, nl)); } } } return -1; } int main() { int n, m; while(scanf("%d %d", &n, &m) == 2) { vector<edge> g; vector<edge> t; for (int i = 0; i < m; ++i) { int u,v,l; scanf("%d %d %d", &u, &v, &l); --u; --v; g.push_back(edge(u, v, l)); } bool connected = kruskal(g, t, n); int cost = -t[0].w; for (int i = 1; i < (int) t.size(); ++i) cost += t[i].w; if (not connected) printf("disconnected\n"); else printf("%d\n", cost); } }
--- c4.s1275.cteam036.spider.cpp.0.spider.cpp +++ c4.s1360.cteam036.spider.cpp.0.spider.cpp @@ -32,21 +32,17 @@ } -edge kruskal(vector<edge> &g, vector<vector<pair<int, int> > > &tree, int n, bool &connected) { +bool kruskal(vector<edge> &g, vector<edge> &tree, int n) { init(n); - tree.assign(n, vector<pair<int, int> > ()); sort(g.begin(), g.end()); - edge emax(-1, -1, 0); - int cnt = 0; + edge e = g.back(); + tree.push_back(e); + merge(e.x, e.y); for(int i = 0; i < (int) g.size(); ++i) { if (find(g[i].x) != find(g[i].y)) { merge(g[i].x, g[i].y); - tree[g[i].x].push_back(make_pair(g[i].y, g[i].w)); - tree[g[i].y].push_back(make_pair(g[i].x, g[i].w)); - ++cnt; - } else - emax = g[i]; + tree.push_back(g[i]); + } } - connected = (cnt == n - 1); - return emax; + return (int) tree.size() == n - 1; } @@ -74,19 +70,9 @@ } -int sum(vector<vector<pair<int, int> > > &t) { - int s = 0; - for (int x = 0; x < (int) t.size(); ++x) - for (int i = 0; i < (int) t[x].size(); ++i) { - s += t[x][i].second; - //printf("%d %d %d\n", x, t[x][i].first, t[x][i].second); - } - return s / 2; -} - int main() { int n, m; while(scanf("%d %d", &n, &m) == 2) { vector<edge> g; - vector<vector<pair<int, int> > > t; + vector<edge> t; for (int i = 0; i < m; ++i) { int u,v,l; @@ -95,11 +81,8 @@ g.push_back(edge(u, v, l)); } - bool connected = true; - edge e = kruskal(g, t, n, connected); - int cost = sum(t) - e.w; - if (e.x < 0) - cost -= e.w; - else - cost -= bfs(t, e.x, e.y); + bool connected = kruskal(g, t, n); + int cost = -t[0].w; + for (int i = 1; i < (int) t.size(); ++i) + cost += t[i].w; if (not connected) printf("disconnected\n");