How to Create a Good Game (AOJ2230)

これは1100だと思う
知識5+,頭3,実装力1,ライブラリ力1

問題:
正の重み付きDAGで,さらに,任意のiに対し0->i->N-1となるpathがあるものが与えられる.0からN-1への最長距離を変えないように辺の重みを0位上の整数増やす.どれだけ増やせるか.N<=100,M<=1000,重み<=1000


双対LPと言われてもさっぱりだとたぶん(頭がかなりおかしくないと)解けないのでググりましょう.


解答:
d[v]=0からvへの最長距離,c[e]=eのもとの重み,a[e]=eに増やす重み とすると,d,aを変数として,次のようなLP定式化が出来る.
subject to
d[v],a[e]>=0
d[t]-d[s]<=D (tはN-1,sは0)
有向辺(u,v)∈Eに対して,d[v]>=d[u]+c[e]+a[e]
(上2つで式がM個)
maximize Σa(e)


これはLPの形になっている.
とりあえず双対を取る←不可能

双対を取ると,変数をy0,y1,...y_Mとして,(y_Mがd[t]-d[s]<=Dに対応)
各v∈Vに対しΣy_i (i:in) -Σy_o (o:out) >=0 ただし,v=sの時は-y_Mを追加,v=tの時は+y_Mを追加というN個の式と,
y_i≧1 (0≦iくM)
というM個の式が出来る
あとはy_i≧0(0≦iくM+1) があって,求めるものは
minimize ( Σ-c[e]*y_e )+ D*y_M
となる.
>=0の式を全て足し合わせると左辺が0になるので,全て=0がわかる.
するとこれは最小費用流に見える.
負のコストを含んだ流量上限なし(+下限あり),全体流量決まってない のやりかたは,
i)下限のぶんは capが下限でコストを-infしたやつ と capが上限-下限でコストそのまま にして流した後答えにinf*下限を足せばOK.(ただし多分下限まで流しきれない時はこれではまずそう)
ii)負のコスト h0の計算だけBellmanFordすればよい.(負辺を含む最小費用流について(Attack the Moles) - sigma425のブログ参照)
iii)全体流量制限なし
h[t]>=0になったらおしまい

良問だと思うけど,解くには圧倒的知識が必要(どっちかというと教育的良問)
あ、あといつのまにか整数係数から実数係数にかわっていたけどそこらへんは完全ユニモジュラみたいな話があるからOKらしいです(まあこれはなんとなくわかりそう(普通のフローの時もそうだったし)(証明が簡単だと言ってるわけではないです))

ちなみに解説スライドでは初めの定式化でd[t]<=Dとしてるけど,双対取った後そのまま最小費用流にならないので,d[t]-d[s]<=Dに変えたほうがいいです.(考察時の話だから実装には関係ないけど)
結果的にはもとの辺の値を負にしたのをcostにしてcapを1にして,最後にN-1からT(つくる)へ(0からN-1への最長距離)コストの辺をはって 流量決まってないmin_cost_flowを流す とかいう意味不明なことをやってるし謎すぎるよね


思考ノート 大体書いてあります
f:id:sigma425:20150712235352j:plain

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef pair<int,int> P;
struct edge {
	int to,cap,cost,rev;
	edge(int a,int b,int c,int d) : to(a),cap(b),cost(c),rev(d){}
};
const int MAX_V=101,INF=2e8,inf=1e6;
int V;			//代入!!
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from, int to, int cap, int cost){
	edge e1=edge(to,cap,cost,G[to].size()),e2=edge(from,0,-cost,G[from].size());
//	printf("%d->%d   cap=%d   cost=%d\n",from,to,cap,cost);
	G[from].push_back(e1);
	G[to].push_back(e2);
}
void add_edge_lbub(int from,int to,int lb,int ub,int cost){
	add_edge(from,to,ub-lb,cost);
	add_edge(from,to,lb,cost-inf);
}
int min_cost_flow(int s, int t){
	int res=0;
	fill(h,h+V,INF);
	h[0]=0;
	rep(v,V){
		for(edge& e:G[v]) if(e.cap!=0) chmin(h[e.to],h[v]+e.cost);
	}
//	rep(v,V) printf("h[%d]=%d\n",v,h[v]);
	int f=INF;
	while(h[t]<0){
		priority_queue< P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();
			que.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;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF) return -1;
		for(int v=0;v<V;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;
}
vector<P> GG[100];
int main(){
	int N,M;
	cin>>N>>M;
	rep(i,M){
		int x,y,s;
		cin>>x>>y>>s;
		add_edge_lbub(x,y,1,INF,-s);
		GG[x].pb(P(y,s));
	}
	int S=0,T=N;
	V=N+1;
	int D=0;
	{
		int d[101]={};
		rep(i,N){
			for(P e:GG[i]){
				chmax(d[e.fs],d[i]+e.sc);
			}
		}
		D=d[N-1];
	}
//	show(D);
	add_edge(N-1,N,INF,D);
	cout<<min_cost_flow(S,T)+M*inf<<endl;
}