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