負辺を含む最小費用流について(Attack the Moles)

AOJ-ICPC

蟻本での最小費用流の扱い方としては,
1.毎回Bellman-Fordで残余グラフ上を見る
2.ポテンシャルhを考えるとdijkstraで出来る
3.(column)負辺ののぞき方紹介(使う本数が必ず等しい場合,負辺を流しきったと考えた時の変形,あとはBellman-Fordを使おうとも書いてある)

今、頂点数NのDAGがあって流量Fの小さい"最大"費用流を求めたい気分だとして、3の"負辺を流しきる変形"をやると、流すフローがNくらい増えるので、オーダーは(F+N)ElogVでN^3くらいになってしまう.

2のdijkstraだが、蟻本をよく読むと"また、負の辺が存在しなければh0の計算にはダイクストラ法を用いることができます。"と書いてある(hiは流量iの最小費用流の残余グラフ上でのsから各vへの距離)
もちろんh0はそのまま最短路問題なので、負辺があればBellman-Fordでも大丈夫(ここではDAGなのでトポロジカルに見るだけ).そこから先は、実はdijkstraで出来る.(蟻本のh_i+1をh_iから計算するところに、元の辺のコストが0以上であることは使われていない)

よってポテンシャルの初期値を先に計算し、あとは最小費用流のコードそのままで負辺を含む最小費用流を計算できます

蟻本に明示的に書いてなかったのでびっくりした(2015.7/12 追記 書いてありました 目ついてますか)

↓Attack the Molesのコード

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(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
typedef pair<int,int> P;
struct edge {int to,cap,cost,rev;};
const int MAX_V=6100,INF=1e9;
int V;			//代入!!
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
int top[MAX_V];
int s,t,l,r;
void add_edge(int from, int to, int cap, int cost){
//	printf("%d->%d  cap=%d,cost=%d\n",from,to,cap,cost);
	edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
	G[from].push_back(e1);
	G[to].push_back(e2);
}
int min_cost_flow(int s, int t, int f){
	int res=0;
	fill(h,h+V,0);
	rep(i,V){
		int v=top[i];
		rep(j,G[v].size()){
			edge &e=G[v][j];
			if(e.cap==0) continue;
			int u=e.to;
			h[u]=min(h[u],h[v]+e.cost);
		}
	}
//	rep(i,V) printf("h[%d]=%d\n",i,h[i]);
	while(f>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;
}
int X[3000],T[3000],p[3000];
vector<P> id;
int main(){
	int N,speed,xl,xr;
	scanf("%d%d%d%d",&N,&speed,&xl,&xr);
	rep(i,N) scanf("%d%d%d",X+i,T+i,p+i);
	s=2*N,t=s+1,l=s+2,r=s+3;
	V=r+1;
	rep(i,N){
		id.pb(P(T[i]*2,i));
		id.pb(P(T[i]*2+1,i+N));
	}
	id.pb(P(-2,s));
	id.pb(P(-1,l));
	id.pb(P(-1,r));
	id.pb(P(INF,t));
	sort(all(id));
	rep(i,V) top[i]=id[i].sc;
	rep(i,N) add_edge(i,i+N,1,-p[i]),add_edge(i,i+N,1,0);
	rep(i,N) rep(j,N){
		if(i==j) continue;
		if((T[j]-T[i])*speed>=abs(X[j]-X[i])) add_edge(i+N,j,2,0);
	}
	rep(i,N){
		if(T[i]*speed>=abs(X[i]-xl)) add_edge(l,i,1,0);
		if(T[i]*speed>=abs(X[i]-xr)) add_edge(r,i,1,0);
	}
	rep(i,N) add_edge(i+N,t,2,0);
	add_edge(s,t,2,0);
	add_edge(s,l,1,0);
	add_edge(s,r,1,0);
	cout<<-min_cost_flow(s,t,2)<<endl;
}