Skip to content

Instantly share code, notes, and snippets.

@MiSawa
Created Mar 19, 2014
Embed
What would you like to do?
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, b, n) for(int i = (b); i < (n); ++i)
#define let(v, x) __typeof(x) v = (x)
#define foreach(i,v) for(let(i, (v).begin());i!=(v).end();i++)
/**
* 割とどうしてくれてもいいけど, 理解 && バグ潰ししてから使うべきです.
*
*/
/**
* Dinic と同じように,
* - 頂点数を取るコンストラクタ
* - add_edge(src, dst, cap)
* - run(s, t)
* の 3 つを備えるクラス (例えば MyDinic) を作って,
*
* Benchmark<Dinic> bm
* を
* Benchmark<Dinic, MyDinic> bm
* とかに変えれば, 比較出来る.
*/
struct Dinic{//{{{
typedef int Cap;
static const Cap INF = 1<<29;
struct E{//{{{
int dst;
Cap cap;
int rev;
E(int dst, Cap cap, int rev) : dst(dst), cap(cap), rev(rev) {}
};//}}}
int n;
vector<vector<E> > g;
Dinic(int n) : n(n), g(n) {}
inline void add_edge(int src, int dst, Cap cap){//{{{
if(src == dst) return;
g[src].push_back(E(dst,cap,g[dst].size()));
g[dst].push_back(E(src, 0 ,g[src].size() - 1));
}//}}}
inline void add_undirected_edge(int src, int dst, Cap cap){//{{{
if(src == dst) return;
g[src].push_back(E(dst,cap,g[dst].size()));
g[dst].push_back(E(src,cap,g[src].size() - 1));
}//}}}
vector<int> level, iter;
Cap dfs(const int &s, const int &u, Cap crr){//{{{
if(s == u || crr == 0) return crr;
Cap sum = 0;
for(int &i = iter[u]; i < g[u].size(); ++i){
E &e = g[u][i], &ee = g[e.dst][e.rev];
const int &v = e.dst; // s -- v - u -- t
if(level[v] >= level[u] || ee.cap <= 0) continue;
Cap f = dfs(s, v, min(crr - sum, ee.cap));
if(f <= 0) continue;
ee.cap -= f; e.cap += f;
sum += f;
if(sum == crr) break;
}
return sum;
}//}}}
Cap run(int s, int t){//{{{
vector<int> q(n);
for(Cap flow = 0; ;){
level.assign(n, -1);
int ql = 0, qr = 0;
level[q[qr++] = s] = 0;
while(ql != qr && level[t] == -1){
int u = q[ql++];
foreach(e, g[u]) if(e->cap > 0 && level[e->dst] == -1)
level[ q[qr++] = e->dst ] = level[u] + 1;
}
if(level[t] == -1) return flow;
iter.assign(n, 0);
flow += dfs(s, t, INF);
}
}//}}}
};//}}}
struct Wave{//{{{
typedef int Cap;
static const Cap INF = 1<<29;
struct E{//{{{
int src, dst;
Cap cap, _cap;
int rev;
E(int src, int dst, Cap cap, int rev) :
src(src), dst(dst), cap(cap), _cap(0), rev(rev) {}
};//}}}
int n;
vector<vector<E> > g;
Wave(int n) : n(n), g(n) {}
inline void add_edge(int src, int dst, Cap cap){//{{{
if(src == dst) return;
g[src].push_back(E(src, dst,cap,g[dst].size()));
g[dst].push_back(E(dst, src, 0 ,g[src].size() - 1));
}//}}}
inline E &rev(const E& e){ return g[e.dst][e.rev]; }
vector<int> level, iter;
vector<int> blocked;
vector<int> unbalance[2]; // { unblocked, blocked }
vector<int> inS;
vector<Cap> ex;
inline void push(E &e){//{{{
Cap f = min(e.cap, ex[e.src]);
if(!inS[e.dst]) unbalance[blocked[e.dst]].push_back(e.dst);
inS[e.dst] = true;
e.cap -= f; rev(e).cap += f;
ex[e.src] -= f; ex[e.dst] += f;
}//}}}
// dir = +1 ? s to t : t to s
inline void discharge(const int& u, const int dir){//{{{
for(int &i = iter[u]; i < g[u].size(); ++i){
E &e = g[u][i];
if(e.cap == 0 || level[e.src] + dir != level[e.dst]) continue;
if(dir == +1 && blocked[e.dst]) continue;
push(e);
if(ex[u] == 0) return;
}
blocked[u] = true;
if(!inS[u]) unbalance[1].push_back(u);
inS[u] = true;
iter[u] = 0;
}//}}}
Cap run(int s, int t){//{{{
vector<int> q(n);
vector<int> tmp; tmp.reserve(n);
rep(i, 2) unbalance[i].reserve(n);
rep(i, 2) unbalance[i].clear();
inS.assign(n, false); inS[s] = inS[t] = true;
for(Cap flow = 0; ;){
level.assign(n, -1);
int ql = 0, qr = 0;
level[q[qr++] = s] = 0;
while(ql != qr && level[t] == -1){
const int &u = q[ql++];
foreach(e, g[u]) if(level[e->dst] == -1 && e->cap + e->_cap > 0)
level[ q[qr++] = e->dst ] = level[u] + 1;
}
if(level[t] == -1) return flow;
rep(i, qr){
if(level[q[i]] == level[t] && q[i] != t){
level[q[i]] = -1; continue;
}
foreach(e, g[q[i]]){
if(level[e->src] + 1 == level[e->dst]){
e->cap += e->_cap; e->_cap = 0;
}else{
e->_cap += e->cap; e->cap = 0;
}
}
}
iter.assign(n, 0);
blocked.assign(n, false);
ex.assign(n, 0); ex[s] = INF; discharge(s, +1); ex[s] = 0;
while(!unbalance[0].empty() || !unbalance[1].empty()){
rep(b, 2) while(!unbalance[b].empty()){
tmp.clear();
int l = level[unbalance[b].back()];
while(!unbalance[b].empty() && level[unbalance[b].back()] == l){
int v = unbalance[b].back(); unbalance[b].pop_back();
inS[v] = false; tmp.push_back(v);
}
foreach(v, tmp) discharge(*v, b ? -1 : +1);
}
}
flow += ex[t];
}
}//}}}
};//}}}
unsigned int xor128(){//{{{
static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
//static unsigned int x=129042, y=38923212, z=3829312, w=3893189;
unsigned int t=x^(x<<11);
x=y;y=z;z=w;
return w=(w^(w>>19))^(t^(t>>8));
}//}}}
int rnd(int m){//{{{
return xor128() % m;
}//}}}
struct Input{//{{{
typedef int Cap;
static const Cap C = 1<<10; // max capacity
struct E{//{{{
int src, dst;
Cap cap;
E(){}
E(int src, int dst, Cap cap) : src(src), dst(dst), cap(cap) {}
};//}}}
vector<E> edges;
int n;
int s, t;
Input(){}
Input(int n, int s, int t) : n(n), s(s), t(t) { }
inline void add_edge(int src, int dst, Cap cap){ add_edge(E(src, dst, cap)); }
inline void add_edge(E e){ edges.push_back(e); }
inline void reset(){ n = s = t = 0; edges.clear(); }
friend istream& operator>>(istream &is, Input& in){//{{{
in.reset();
int m;
is >> in.n >> m;
is >> in.s >> in.t;
rep(i, m){
int src, dst; Cap cap;
is >> src >> dst >> cap;
in.add_edge(src, dst, cap);
}
return is;
}//}}}
friend ostream& operator<<(ostream &os, const Input& in){//{{{
os << in.n << " " << in.edges.size() << endl;
os << in.s << " " << in.t << endl;
foreach(it, in.edges)
os << it->src << " " << it->dst << " " << it->cap << endl;
return os;
}//}}}
static Input random(int n, int m){//{{{
Input res(n, 0, n-1);
rep(i, m){
E e;
e.src = rnd(n); e.dst = rnd(n); e.cap = rnd(C);
while(e.src == e.dst) e.dst = rnd(n);
res.add_edge(e);
}
return res;
}//}}}
static Input random_dense(int n){//{{{
Input res(n, 0, n-1);
rep(i, n) rep(j, n) if(i != j) if(rnd(2)) res.add_edge(i, j, rnd(C));
return res;
}//}}}
static Input random_complete(int n){//{{{
Input res(n, 0, n-1);
rep(i, n) rep(j, n) if(i != j) res.add_edge(i, j, rnd(C));
return res;
}//}}}
// http://deepblue.lib.umich.edu/handle/2027.42/29530
// k+1 頂点, 2k-1 辺
static Input worst_dinic1(int k){//{{{
Input res(k+1, 0, k);
rep(i, k) res.add_edge(i, k, 1);
rep(i, k-1) res.add_edge(i, i+1, k+1);
return res;
}//}}}
// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited
// 6k-2 頂点, 3k^2 + 4k - 4 辺
static Input worst_dinic2(int k){//{{{
const Cap INF = 1<<25;
const int q = k-1, n = 6*k - 2;
const int src = 0, dst = 1;
int a = 2;
const int sb = a, se = a+=k;
const int tb = a, te = a+=k;
const int ub = a, ue = a+=2*q;
const int vb = a, ve = a+=2*q;
Input res(n, src, dst);
REP(s, sb, se) res.add_edge(src, s, k);
REP(t, tb, te) res.add_edge(t, dst, k);
REP(s, sb, se) REP(t, tb, te) res.add_edge(s, t, 1);
res.add_edge(src, ub, INF); res.add_edge(vb, dst, INF);
REP(u, ub, ue-1) res.add_edge(u, u+1, INF);
REP(v, vb, ve-1) res.add_edge(v+1, v, INF);
for(int u = ub+1; u < ue; u += 4) REP(t, tb, te)
res.add_edge(u, t, k);
for(int u = ub+3; u < ue; u += 4) REP(s, sb, se)
res.add_edge(u, s, k);
for(int v = vb+1; v < ve; v += 4) REP(s, sb, se)
res.add_edge(s, v, k);
for(int v = vb+3; v < ve; v += 4) REP(t, tb, te)
res.add_edge(t, v, k);
return res;
}//}}}
};//}}}
struct Timer{//{{{
clock_t t;
Timer() {reset();}
void reset(){t = clock();}
double getTime(){return ((double)clock()-(double)t)/(double)CLOCKS_PER_SEC;}
void print(){ printf("runtime: %.3f seconds\n", getTime()); }
};//}}}
namespace U{//{{{
template<typename T> string to_s(T t){ //{{{
stringstream ss;
ss << t;
return ss.str();
} //}}}
#include<cxxabi.h>
template<typename T> string classname(){//{{{
char *p;
int status = 0;
p = abi::__cxa_demangle(typeid(T).name(), 0, 0, &status);
string res = p;
free(p);
return res;
}//}}}
};//}}}
template<typename ... Solvers> struct Benchmark{//{{{
typedef int Cap;
map<string, double> time;
template<typename T> Cap _run(const Input& in){//{{{
T solver(in.n);
foreach(e, in.edges) solver.add_edge(e->src, e->dst, e->cap);
Timer timer;
Cap res = solver.run(in.s, in.t);
time[U::classname<T>()] += timer.getTime();
return res;
}//}}}
template<typename T0, typename T1, typename ... T> Cap _run(const Input& in){//{{{
double a = _run<T0>(in);
double b = _run<T1, T...>(in);
assert(a == b);
return a;
}//}}}
void run(const Input& in){ _run<Solvers...>(in); }
void reset(){ time.clear(); }
void print(){//{{{
cout.setf(ios::fixed);
cout.precision(3);
foreach(it, time){
cout << left << setw(30) << it->first << ": ";
cout << left << setw(6) << it->second << " sec" << endl;
}
}//}}}
};//}}}
/*
|* ケース |* 頂点数 |* 辺数 |
| ランダムを80ケース(合計) | 5000 | 1000000 |
| ランダムを40ケース(合計) | 50000 | 1000000 |
| ランダムを13ケース(合計) | 500000 | 1000000 |
| 密なランダムを5ケース(合計) | 5000 | 約 [tex:n(n-1)/2] |
| 完全グラフを15ケース(合計) | 2000 | [tex:n(n-1)] |
| ワーストケース1つ目 | 7000 | 13997 |
| ワーストケース2つ目 | 628 | 33491 |
*/
void test(int c){
Benchmark<Dinic, Wave> bm;
Input in;
int T;
if(c == 0 || c == -1){ // ランダムを80ケース(合計) n=5000, m=1000000//{{{
bm.reset();
T = 80;
rep(i, T){
Input in = Input::random(5000, 1000000);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 1 || c == -1){ // ランダムを40ケース(合計) n=50000, m=1000000//{{{
bm.reset();
T = 40;
rep(i, T){
Input in = Input::random(50000, 1000000);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 2 || c == -1){ // ランダムを13ケース(合計) n=500000, m=1000000//{{{
bm.reset();
T = 13;
rep(i, T){
Input in = Input::random(500000, 1000000);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 3 || c == -1){ // 密なランダムを5ケース(合計) n=5000 //{{{
bm.reset();
T = 5;
rep(i, T){
Input in = Input::random_dense(5000);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 4 || c == -1){ // 完全グラフを15ケース(合計) n=2000 //{{{
bm.reset();
T = 15;
rep(i, T){
Input in = Input::random_complete(2000);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 5 || c == -1){ // ワーストケース1つ目 n=7000 //{{{
bm.reset();
T = 1;
rep(i, T){
Input in = Input::worst_dinic1(6999);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
if(c == 6 || c == -1){ // ワーストケース2つ目 k=105 //{{{
bm.reset();
T = 1;
rep(i, T){
Input in = Input::worst_dinic2(105);
cout << "case " << i << " (n = " << in.n << ", m = " << in.edges.size() << ")" << endl;
bm.run(in);
}
bm.print();
}//}}}
}
int main(){
test(6);
return 0;
Benchmark<Dinic> bm;
Input in;
//cin >> in;
//in = Input::worst_dinic1(6999);
//cout << in.n << ", " << in.edges.size() << endl;
//bm.run(in);
////bm.print();
//return 0;
bm.reset();
const int T = 15;
rep(i, T){
cout << "Case " << i+1 << "..." << flush;
//Input in = Input::random(500000, 1000000);
//Input in = Input::random_dense(5000);
Input in = Input::random_complete(2000);
//cout << in << endl;
bm.run(in);
cout << endl;
}
bm.print();
return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment