2017-2018 ACM-ICPC, Asia Daejeon Regional Contest E - How Many to Be Happy?
クラスカルのようにコストが小さい辺から追加していくことを考える.コストがの辺を追加しようとしているときにサイクルが存在する場合,その辺をMSTに含めることができない.サイクルが存在しないようにするために削除する必要のある辺の本数は最小カットを用いて求めることができる.辺の数の回数,最大フローを計算することで答えを求められる.
最大流量が なのでFord-Fulkersonを使うと ,全ての辺のコストが1なのでdinicを使うと になる.
dinic の計算量
- 最悪計算量
- 二部グラフの最大マッチング(いわゆるHopcroft-Karp)
二部グラフ+超頂点2つ が常に なわけではない My Algorithm : kopricky アルゴリズムライブラリ Bipartite Matching Algorithm - グラフの辺コストが全て同じ
- 最大流量が
- 最大辺容量が コストスケーリングで
の順に 単位でフローを流す - ランダムケース だいたい早い
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; template<class T> struct dinic { struct edge{ int to; T cap; int rev; bool isrev; }; vector<vector<edge>> G; vector<int> level, iter; void bfs(int s) { level.assign(G.size(), -1); queue<int> que; level[s] = 0; que.push(s); while(que.size()) { int v = que.front(); que.pop(); for(auto i: G[v]) { if(i.cap > 0 && level[i.to] < 0) { level[i.to] = level[v] + 1; que.push(i.to); } } } } T dfs(int v, const int t, T f) { if(v == t) return f; for(int &i = iter[v]; i<(ll)G[v].size(); ++i) { edge &e = G[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { T d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } dinic() {} dinic(int n) : G(n), level(n), iter(n) {} void add_edge(int from, int to, T cap) { G[from].push_back({to, cap, (int)G[to].size(), false}); G[to].push_back({from, 0, (int)G[from].size()-1, true}); } // sからtへ流量fを流す T maxflow(int s, int t, T f = 1LL<<30) { T flow = 0; while(1) { bfs(s); if(level[t] < 0) return flow; iter.assign(G.size(), 0); T tmp; while((tmp = dfs(s, t, f)) > 0) flow += tmp; } } friend ostream &operator <<(ostream& out, const dinic& a){ out << endl; for(int i = 0; i < (int)a.G.size(); i++) { for(auto &e : a.G[i]) { if(e.isrev) continue; auto &rev_e = a.G[e.to][e.rev]; out << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } return out; } }; int main(void) { ll n, m; cin >> n >> m; vector<vector<PII>> edges(501); REP(i, m) { ll a, b, c; cin >> a >> b >> c; a--, b--; edges[c].push_back({a, b}); } ll ret = 0; FOR(i, 1, 501) { for(auto e: edges[i]) { dinic<ll> graph(n); REP(j, i) for(auto f: edges[j]) { graph.add_edge(f.first, f.second, 1); graph.add_edge(f.second, f.first, 1); } ret += graph.maxflow(e.first, e.second); } } cout << ret << endl; return 0; }