Submission #61685
Source Code Expand
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; const int kInf = (1 << 30) - 1; struct Edge { int u, v, cost; bool operator<(const Edge& other) const { return cost < other.cost; } }; template <typename Set, typename T> bool contains(const Set& c, const T& value) { return c.find(value) != c.end(); } bool find_cycle(const vector<Edge>& e, int k, int k0, set<int>* cycle) { if (cycle->find(k) != cycle->end()) { return true; } cycle->insert(k); for (size_t i = 0; i < e.size(); i++) { if (e[i].u == k && e[i].v != k0) { if (find_cycle(e, e[i].v, k, cycle)) return true; } if (e[i].v == k && e[i].u != k0) { if (find_cycle(e, e[i].u, k, cycle)) return true; } } cycle->erase(k); return false; } int solve(const vector<Edge>& e, int k, const set<int>& cycle) { int sum = 0; vector<Edge>::const_iterator p = e.begin(); while(k > 0) { if (p == e.end()) { return kInf; } if (!contains(cycle, p->u) || !contains(cycle, p->v)) { sum += p->cost; --k; } ++p; } return sum; } int main() { int n, m, k; cin >> n >> m >> k; vector<Edge> e(m); for (int i = 0; i < m; i++) { cin >> e[i].u >> e[i].v >> e[i].cost; --e[i].u, --e[i].v; } sort(e.begin(), e.end()); vector<int> g(n); set<int> cycle; for (int i = 0; i < n; i++) { g[i] = i; } for (int i = 0; i < m; i++) { int g1 = g[e[i].u], g2 = g[e[i].v]; if (g1 == g2) { find_cycle(e, e[i].u, -1, &cycle); } else { replace(g.begin(), g.end(), max(g1, g2), min(g1, g2)); } } sort(g.begin(), g.end()); int k0 = unique(g.begin(), g.end()) - g.begin(); int ans = solve(e, k - k0, cycle); int cut = -1; for (int i = 0; i < m; i++) { if (contains(cycle, e[i].u) && contains(cycle, e[i].v)) { int extra_cost = e[i].cost; e.erase(e.begin() + i); ans = min(ans, solve(e, k - k0, set<int>()) + extra_cost); break; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | yuizumi |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 2348 Byte |
Status | AC |
Exec Time | 25 ms |
Memory | 816 KB |
Judge Result
Set Name | nonloop | loop | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 70 / 70 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
nonloop | nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt |
loop | loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
loop/case_000.txt | AC | 21 ms | 784 KB |
loop/case_001.txt | AC | 19 ms | 792 KB |
loop/case_002.txt | AC | 21 ms | 788 KB |
loop/case_003.txt | AC | 21 ms | 792 KB |
loop/case_004.txt | AC | 21 ms | 768 KB |
loop/case_005.txt | AC | 20 ms | 784 KB |
loop/case_006.txt | AC | 20 ms | 696 KB |
loop/case_007.txt | AC | 21 ms | 792 KB |
loop/case_008.txt | AC | 20 ms | 692 KB |
loop/case_009.txt | AC | 20 ms | 808 KB |
loop/case_010.txt | AC | 20 ms | 792 KB |
loop/case_011.txt | AC | 21 ms | 792 KB |
loop/case_012.txt | AC | 21 ms | 788 KB |
loop/case_013.txt | AC | 19 ms | 792 KB |
loop/case_014.txt | AC | 21 ms | 784 KB |
loop/case_015.txt | AC | 20 ms | 692 KB |
loop/case_016.txt | AC | 20 ms | 784 KB |
loop/case_017.txt | AC | 21 ms | 696 KB |
loop/case_018.txt | AC | 19 ms | 784 KB |
loop/case_019.txt | AC | 19 ms | 784 KB |
loop/case_020.txt | AC | 21 ms | 640 KB |
loop/case_021.txt | AC | 20 ms | 788 KB |
loop/case_022.txt | AC | 21 ms | 788 KB |
loop/case_023.txt | AC | 23 ms | 664 KB |
loop/case_024.txt | AC | 20 ms | 784 KB |
loop/case_025.txt | AC | 21 ms | 692 KB |
loop/case_026.txt | AC | 21 ms | 784 KB |
loop/case_027.txt | AC | 22 ms | 776 KB |
loop/case_028.txt | AC | 21 ms | 780 KB |
loop/case_029.txt | AC | 21 ms | 780 KB |
loop/case_030.txt | AC | 23 ms | 640 KB |
loop/case_031.txt | AC | 20 ms | 792 KB |
loop/case_032.txt | AC | 21 ms | 800 KB |
loop/case_033.txt | AC | 21 ms | 780 KB |
loop/loop_case_000.txt | AC | 20 ms | 792 KB |
loop/loop_case_001.txt | AC | 22 ms | 792 KB |
loop/loop_case_002.txt | AC | 19 ms | 792 KB |
loop/loop_case_003.txt | AC | 19 ms | 788 KB |
loop/loop_case_004.txt | AC | 20 ms | 792 KB |
loop/loop_case_005.txt | AC | 19 ms | 784 KB |
loop/loop_case_006.txt | AC | 21 ms | 676 KB |
loop/loop_case_007.txt | AC | 21 ms | 692 KB |
loop/loop_case_008.txt | AC | 20 ms | 792 KB |
loop/loop_case_009.txt | AC | 19 ms | 792 KB |
loop/loop_case_010.txt | AC | 20 ms | 780 KB |
loop/loop_case_011.txt | AC | 21 ms | 784 KB |
loop/loop_case_012.txt | AC | 19 ms | 780 KB |
loop/loop_case_013.txt | AC | 20 ms | 788 KB |
loop/loop_case_014.txt | AC | 21 ms | 784 KB |
loop/loop_case_015.txt | AC | 20 ms | 788 KB |
loop/loop_case_016.txt | AC | 20 ms | 792 KB |
loop/loop_case_017.txt | AC | 21 ms | 768 KB |
loop/loop_case_018.txt | AC | 21 ms | 784 KB |
loop/loop_case_019.txt | AC | 20 ms | 788 KB |
loop/loop_case_020.txt | AC | 19 ms | 788 KB |
loop/loop_case_021.txt | AC | 21 ms | 792 KB |
loop/loop_case_022.txt | AC | 19 ms | 684 KB |
loop/loop_case_023.txt | AC | 20 ms | 784 KB |
loop/loop_case_024.txt | AC | 19 ms | 792 KB |
loop/loop_case_025.txt | AC | 20 ms | 788 KB |
loop/loop_case_026.txt | AC | 20 ms | 792 KB |
loop/loop_case_027.txt | AC | 19 ms | 784 KB |
loop/loop_case_028.txt | AC | 21 ms | 792 KB |
loop/loop_case_029.txt | AC | 21 ms | 788 KB |
loop/loop_case_030.txt | AC | 22 ms | 788 KB |
loop/loop_case_031.txt | AC | 21 ms | 784 KB |
nonloop/case_000.txt | AC | 21 ms | 788 KB |
nonloop/case_001.txt | AC | 20 ms | 780 KB |
nonloop/case_002.txt | AC | 19 ms | 788 KB |
nonloop/case_003.txt | AC | 20 ms | 784 KB |
nonloop/case_004.txt | AC | 21 ms | 784 KB |
nonloop/case_005.txt | AC | 20 ms | 796 KB |
nonloop/case_006.txt | AC | 20 ms | 792 KB |
nonloop/case_007.txt | AC | 20 ms | 784 KB |
nonloop/case_008.txt | AC | 21 ms | 784 KB |
nonloop/case_009.txt | AC | 21 ms | 632 KB |
nonloop/case_010.txt | AC | 21 ms | 796 KB |
nonloop/case_011.txt | AC | 20 ms | 764 KB |
nonloop/case_012.txt | AC | 19 ms | 688 KB |
nonloop/case_013.txt | AC | 20 ms | 788 KB |
nonloop/case_014.txt | AC | 20 ms | 796 KB |
nonloop/case_015.txt | AC | 21 ms | 788 KB |
nonloop/case_016.txt | AC | 20 ms | 808 KB |
nonloop/case_017.txt | AC | 25 ms | 780 KB |
nonloop/case_018.txt | AC | 21 ms | 788 KB |
nonloop/case_019.txt | AC | 21 ms | 792 KB |
nonloop/case_020.txt | AC | 21 ms | 788 KB |
nonloop/case_021.txt | AC | 21 ms | 656 KB |
nonloop/case_022.txt | AC | 21 ms | 788 KB |
nonloop/case_023.txt | AC | 20 ms | 796 KB |
nonloop/case_024.txt | AC | 21 ms | 788 KB |
nonloop/case_025.txt | AC | 21 ms | 796 KB |
nonloop/case_026.txt | AC | 19 ms | 788 KB |
nonloop/case_027.txt | AC | 19 ms | 788 KB |
nonloop/case_028.txt | AC | 19 ms | 784 KB |
nonloop/case_029.txt | AC | 21 ms | 792 KB |
nonloop/case_030.txt | AC | 20 ms | 668 KB |
nonloop/case_031.txt | AC | 21 ms | 700 KB |
nonloop/case_032.txt | AC | 20 ms | 816 KB |
nonloop/case_033.txt | AC | 20 ms | 696 KB |