POJ 3680: Intervals - omochan's diary

解法は蟻本にある。

蟻本では負辺にあらかじめ目一杯流すことで対応しているが、ここではベルマンフォードで最初のポテンシャルを求めることによって解いてみよう。

ポテンシャルh(v):=(s-v間の最短距離)と基本的にすれば良いが、以下のコードの方が単純。

memset(h, 0, sizeof(h));
rep(k, 0, V) {
	rep(i, 0, V) {
		rep(j ,0, (int)G[i].size()) {
			edge &e = G[i][j];
			if(e.cap == 0) continue;
			MIN(h[e.to], h[i] + e.cost);
		}
	}
}

これでもいい理由を考えよう。
ある有向辺(u,v)(cost = ce)について、
ce<0の時、h(v)<=h(u)+ceが成立。よってce'=h(u)-h(v)+ce>=0より条件を満たす。

ce>0の時、h(v)が普通のベルマンフォードで正になるような更新が来てもh(v)=0となる。よって得られるはずであったh(v)の値をh'(v)とすれば、h(v)<=0<=h'(v)<=h(u)+ceが成立。ce<0と同じ理由で条件を満たす。

最小費用流の計算量をまじめに考えたことがなかったので考察すると、
|F|に最短経路を見つけるだけのオーダーがかかる。
つまりdijkstraで最短経路を求めているのならO(|F||E|log|V|)
bellman-fordならO(|F||V|^2)である。
密なグラフならbellman-fordの方が速いことに留意する。

全体

namespace MCF { //init before you use it

	struct edge { int to, cap, cost, rev; };

	int V; //num of vertex
	vector<edge> G[MAX_V];
	int h[MAX_V];
	int dist[MAX_V];
	int prevv[MAX_V], preve[MAX_V];

	void init(int v) { //other things don't have to be init.
		V = v;
		rep(i, 0, v) G[i].clear();
	}

	void add_edge(int from, int to, int cap, int cost) {
		G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
		G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
	}

	int get(int s, int t, int f) {
		int res = 0;
		memset(h, 0, sizeof(h));
		//add if the graph includes negative edges
		rep(k, 0, V) {
			rep(i, 0, V) {
				rep(j ,0, (int)G[i].size()) {
					edge &e = G[i][j];
					if(e.cap == 0) continue;
					MIN(h[e.to], h[i] + e.cost);
				}
			}
		}
		
		while(f > 0) {
			priority_queue<pi, vector<pi>, greater<pi> > que;
			fill(dist, dist + V, inf);
			dist[s] = 0;
			que.push(pi(0, s));
			while(!que.empty()) {
				pi p = que.top(); que.pop();
				int v = p.sec;
				if(dist[v] < p.fst) continue;
				rep(i, 0, (int)G[v].size()) {
					edge &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push(pi(dist[e.to], e.to));
					}
				}
			}

			if(dist[t] == inf) return -1;
			rep(v, 0, V) h[v] += dist[v];

			int d = f;
			for(int v = t; v != s; v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d * h[t];
			for(int v = t; v != s; v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}
}

int N, K, Q;
int a[MAX_N], b[MAX_N], w[MAX_N];

int main() {
	scanf("%d", &Q);
	while(Q--) {
		scanf("%d%d", &N, &K);
		rep(i, 0, N) scanf("%d%d%d", &a[i], &b[i], &w[i]);

		vector<int> x;
		rep(i, 0, N) {
			x.push_back(a[i]);
			x.push_back(b[i]);
		}
		sort(all(x));
		x.erase(unique(all(x)), x.end());

		int m = (int)x.size();
		int s = m, t = m + 1;
		MCF::init(m + 2);
		MCF::add_edge(s, 0, K, 0);
		MCF::add_edge(m - 1, t, K, 0);

		rep(i, 0, m - 1) MCF::add_edge(i, i + 1, inf, 0);

		rep(i, 0, N) {
			int u = find(x.begin(), x.end(), a[i]) - x.begin();
			int v = find(x.begin(), x.end(), b[i]) - x.begin();
			MCF::add_edge(u, v, 1, -w[i]);
		}
		printf("%d\n", -MCF::get(s, t, K));
	}
	return 0;