pastebin

Paste #sIG -- näytä pelkkänä tekstinä -- uusi tämän pohjalta

Värjäys: Tyyli: ensimmäinen rivinumero: Tabin korvaus: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
typedef long long llint;

namespace Circu {
	const int MAXV = 500;
	const int MAXE = 500;

	int V, E;
	int how[MAXV], good[MAXV], bio[MAXV], cookie = 1; llint dist[MAXV];
	int from[MAXE], to[MAXE]; llint cap[MAXE], cost[MAXE];

	void init(int n) { V = n; E = 0; }

	void edge(int x, int y, llint c, llint w) {
		from[E] = x; to[E] = y; cap[E] = c; cost[E] = +w; ++E;
		from[E] = y; to[E] = x; cap[E] = 0; cost[E] = -w; ++E;
	}

	void reset() {
		REP(i, V) dist[i] = 0;
		REP(i, V) how[i] = -1;
	}

	bool relax() {
		bool ret = false;
		REP(e, E) if (cap[e]) {
			int x = from[e];
			int y = to[e];

			if (dist[x] + cost[e] < dist[y]) {
				dist[y] = dist[x] + cost[e];
				how[y] = e;
				ret = true;
			}
		}
		return ret;
	}

	llint cycle(int s, bool flip = false) {
		llint sum = 0;
		int x = s;
		do {
			int e = how[x];
			if (flip) --cap[e], ++cap[e^1];
			sum += cost[e];
			x = from[e];
		} while (x != s);
		return sum;
	}

	llint push(int x) {
		for (++cookie; bio[x] != cookie; x = from[how[x]]) {
			if (!good[x] || how[x] == -1 || cap[how[x]] == 0) return 0;
			bio[x] = cookie;
			good[x] = false;
		}
		return cycle(x) >= 0 ? 0 : cycle(x, true);
	}

	llint run() {
		reset();
		llint ret = 0;
		REP(step, 2*V) {
			if (step == V) reset();
			if (!relax()) continue;

			REP(i, V) good[i] = true;
			REP(i, V) if (llint w = push(i)) ret += w, step = 0;
		}
		return ret;
	}
}

int ns=1;

pair<int, int> genBadGraph(llint k){
	if (k==1){
		int s=ns++;
		int t=ns++;
		int v1=ns++;
		int v2=ns++;
		Circu::edge(v1, v2, 1, -1);
		Circu::edge(s, v1, 1, -1);
		Circu::edge(s, v2, 1, -1);
		Circu::edge(v1, t, 1, -1);
		Circu::edge(v2, t, 1, -1);
		return {s, t};
	}
	else{
		int s=ns++;
		int t=ns++;
		pair<int, int> r=genBadGraph(k-1);
		llint c=(1ll<<k);
		Circu::edge(s, r.first, c, -1);
		Circu::edge(s, r.second, c, -1);
		Circu::edge(r.first, t, c, -1);
		Circu::edge(r.second, t, c, -1);
		return {s, t};
	}
}

int main(){
	Circu::init(100);
	pair<int, int> st=genBadGraph(24);
	Circu::edge(st.second, st.first, 1e9, 0);
	cout<<"Vertices "<<ns<<endl;
	cout<<"Edges "<<Circu::E<<endl;
	cout<<Circu::run()<<endl;
}