東京工業大学プログラミングコンテスト2015 : N - 何かグラフの問題

これは自力で解けた。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_n

問題

N頂点M有向辺のグラフがある。

各頂点iに実数A[i]を割り当てるとする。
一部の頂点はA[i]が固定されており、残りは任意に決められる。

各辺u→vにコストcが割り当てられているとき、各辺についてA[u]+c≦A[v]+Tを満たすような最小のTを求めよ。

解法

多くの変数があるとき、うち２変数間x,yの関係がy≦x+Zのような１次不等式で表現できるとき、x→yにコストZの辺を張ったグラフにおいて負のコストの閉路が無ければ、各変数に条件を満たす有効な値の割り当てができる。
今回の問題はまさにこの条件が適用できるので、Tを二分探索して負のコストの閉路ができるTの最小値を求めればよい。

一部頂点はA[i]が固定されているが、ここはA[0]=0となるダミー頂点0を追加し、A[i]≦A[0]A[i]より、0→iにコストA[i]、i→0にコスト-A[i]の辺を張ることで表現できる。

template<class V,int MV> class Bellman_Ford {
public:
	int NV;
	V cost[MV];
	vector<pair<int,V> > E[MV];
	
	void add_edge(int from,int to,V cost){ E[from].push_back(make_pair(to,cost));}
	bool calc(int start,int NV) { // true:ok false:cycle
		int i,j,k;
		FOR(i,NV) cost[i]=1e10;
		cost[start]=0;
		FOR(i,NV) {
			bool up=false;
			FOR(j,NV) FOR(k,E[j].size()) {
				if(cost[E[j][k].first]>cost[j]+E[j][k].second) cost[E[j][k].first]=cost[j]+E[j][k].second, up=true;
			}
			if(!up) return true;
		}
		return false;
	}
};

int N,M,K;
int FIX[3030];
int U[3030],V[3030],C[3030];

bool ok(double T) {
	Bellman_Ford<double,3030> bf;
	int i,x,y;
	
	FOR(i,N) if(FIX[i]!=1<<30) {
		bf.add_edge(0,i+1,FIX[i]);
		bf.add_edge(i+1,0,-FIX[i]);
	}
	FOR(i,M) bf.add_edge(V[i],U[i],T-C[i]);
	return bf.calc(0,N+1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) FIX[i]=1<<30;
	FOR(i,K) cin>>x>>y, FIX[x-1]=y;
	FOR(i,M) cin>>U[i]>>V[i]>>C[i];
	
	double L=-1e10,R=1e10;
	while(R-L>1e-8) {
		double M=(L+R)/2;
		if(ok(M)) R=M;
		else L=M;
	}
	
	if(L<-1e9) _P("#\n");
	else _P("%.12lf\n",L);
	
}

まとめ

すんなり思いつけて良かった。