Go to diff to previous submission
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; struct edge { int u, v, l; bool operator<(const edge & rhs) const { return l < rhs.l; } }; vector<int> UF; vector<int> CS; int find_set(int n) { if (n != UF[n]) UF[n] = find_set(UF[n]); return UF[n]; } bool connected(int u, int v) { return (find_set(u) == find_set(v)); } void connect(int u, int v) { int uroot = find_set(u); int vroot = find_set(v); UF[uroot] = UF[vroot]; } int main() { ios_base::sync_with_stdio(false); int N, M; while (cin >> N) { cin >> M; vector<edge> E (M); // load and sort for (int i = 0; i < M; ++i) { edge e; cin >> e.u >> e.v >> e.l; E[i] = e; } sort (E.begin(), E.end()); // UF UF = vector<int> (N+1); for (int i = 0; i <= N; ++i) UF[i] = i; vector<int> st; long netl = 0; int ei = 0; int ec = 0; while (ei < M && ec < N-2) { edge e = E[ei]; if (!connected(e.u, e.v)) { connect(e.u, e.v); netl += e.l; ++ec; st.push_back(ei); } ++ei; } long minnetl = LONG_MAX; for (int skip = 0; skip < N-1; ++skip) { netl -= st[skip]; // UF UF = vector<int> (N+1); for (int i = 0; i <= N; ++i) UF[i] = i; for (int i = 0; i < N-1; ++i) if (i != skip) connect(E[st[i]].u, E[st[i]].v); for (int ei = M-1; ei >= 0; --ei) { edge e = E[ei]; if (!connected(e.u, e.v)) { connect(e.u, e.v); netl -= e.l; ++ec; } } if (ec == N-1) minnetl = min(minnetl, netl); netl += st[skip]; } if (minnetl < INT_MAX) cout << minnetl << '\n'; else cout << "disconnected\n"; } return 0; }
--- c4.s908.cteam012.spider.cpp.0.spider.cpp +++ c4.s1400.cteam012.spider.cpp.0.spider.cpp @@ -2,4 +2,5 @@ #include <vector> #include <algorithm> +#include <climits> using namespace std; @@ -22,11 +23,9 @@ return (find_set(u) == find_set(v)); } -int connect(int u, int v) +void connect(int u, int v) { int uroot = find_set(u); int vroot = find_set(v); UF[uroot] = UF[vroot]; - CS[uroot] = CS[vroot] = CS[uroot] + CS[vroot]; - return CS[uroot]; } @@ -38,13 +37,4 @@ cin >> M; vector<edge> E (M); - UF = vector<int> (N+1); - CS = vector<int> (N+1); - long netl = 0; - - // UF - for (int i = 0; i <= N; ++i) { - UF[i] = i; - CS[i] = 1; - } // load and sort @@ -56,23 +46,49 @@ sort (E.begin(), E.end()); - // connect longest - edge longest = E.back(); - netl -= longest.l; - connect(longest.u, longest.v); - E.pop_back(); --M; - - bool all = false; int ei = 0; - while (ei < M && !all) { + // UF + UF = vector<int> (N+1); + for (int i = 0; i <= N; ++i) + UF[i] = i; + vector<int> st; + long netl = 0; + int ei = 0; int ec = 0; + while (ei < M && ec < N-2) { edge e = E[ei]; if (!connected(e.u, e.v)) { - if (connect(e.u, e.v) == N) - all = true; + connect(e.u, e.v); netl += e.l; + ++ec; + st.push_back(ei); } ++ei; } - if (all) cout << netl << '\n'; - else cout << "disconnected\n"; + long minnetl = LONG_MAX; + for (int skip = 0; skip < N-1; ++skip) { + netl -= st[skip]; + // UF + UF = vector<int> (N+1); + for (int i = 0; i <= N; ++i) + UF[i] = i; + for (int i = 0; i < N-1; ++i) + if (i != skip) + connect(E[st[i]].u, E[st[i]].v); + for (int ei = M-1; ei >= 0; --ei) { + edge e = E[ei]; + if (!connected(e.u, e.v)) { + connect(e.u, e.v); + netl -= e.l; + ++ec; + } + } + + if (ec == N-1) + minnetl = min(minnetl, netl); + + netl += st[skip]; + } + + if (minnetl < INT_MAX) cout << minnetl << '\n'; + else cout << "disconnected\n"; } return 0;