AOJ 2230: How to Create a Good Game

LPであることと、フローっぽいことはなんとなく分かるけど、最小費用流のLP双対の形にするのが少し難しいので、1100妥当だと思う。

解法

最小費用流の双対なので、変形してから流す。
ネットワークが少し特殊な形をしてるけど、蟻本とかで調べるとやり方が書いてある。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<long, long> P;
#define V 10010
long INF2 = 400000, INF = 1e9;

struct edge {
  long to, cap, cost, rev;

};
typedef vector<edge> vertex;
typedef vector<vertex> graph;
long dist[V];
long h[V];
long prevv[V], preve[V];

vertex g[V];

void add_edge(int from, int to, int cap, int cost){
	//cout<<from<<" "<<to<<" "<<cap<<" "<<cost<<endl;
	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});
}

long min_cost_flow(int s, int t, long f){
	long res = 0;
	fill(h, h+V, 0);
	for(int i = 0; i < V; i++){
		for(int j = 0; j < g[i].size(); j++){
			edge &e = g[i][j];
			if(e.cap == 0) continue;
			int u = e.to;
			h[u] = min(h[u], h[i]+e.cost);
		}
	}
	while(f>0){
		priority_queue<P, vector<P>, greater<P> > q;
		fill(dist, dist+V, INF);
		dist[s] = 0;
		q.push(P(0,s));
		while(!q.empty()){
			P p = q.top(); q.pop();
			int v = p.second;
			if(dist[v] < p.first) continue;
			for(int i = 0; i < g[v].size(); i++){
				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;
					q.push(P(dist[e.to],e.to));
				}
			}
		}
		for(int v = 0; v < V; v++)h[v] += dist[v];

		long 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;
}

#define N 1100
long f[N][N];
long d[N];

int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	int s = 0, t = n-1, t2 = n;
	for(int i = 0; i < n; i++) fill(f[i], f[i]+N, INF);
	for(int i = 0; i < m; i++){
		int x, y, c;
		scanf("%d%d%d",&x,&y,&c);
		c *= -1;
		f[x][y] = c;
		add_edge(x, y, INF, c);
		add_edge(x, y, 1, c-INF2);
	}
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
	add_edge(t, t2, INF, -f[0][n-1]);
	long res = min_cost_flow(s, t2, INF2);
	res += INF2*m;
	printf("%ld\n", res);
	return 0;
}