UTPC2013 H Asteroids2

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_08）

NxNの二次元グリッドに石がM個ある。
i番目の石は(x[i], y[i])にあって、強さの和がa[i]以上b[i]以下になるようレーザーを当てる。

レーザーはx軸に平行またはy軸に平行な直線にそってしか撃てない。
x = kに撃てるレーザーの強さは0以上p[k]以下、
y = kに撃てるレーザーの強さは0以上q[k]以下。

軸にそって撃ったレーザーは直線上にある全ての石を貫通して当たる。

このとき全ての石に制約を満たすように当てるレーザーの当て方があるかどうかを判定せよ。

制約条件

N≦1000
M≦10^5
p[i], q[i]≦10^6
a[i], b[i]≦2*10^6

方針

どうみても牛ゲー。

制約を不等式で書く。x = iで発射するレーザーの強さをxi,
y = iで発射するレーザーの強さをyiとする。

0≦xi≦p[i], 0≦yi≦q[i]
j番目の石について、a[j]≦x_x[j] + y_y[j]≦b[j]

で、牛ゲー化するためには、不等式が全て
xi - xj ≦ const
の形をしていなければならないが、
ゼロの変数を導入するのと、
yi = -x_(i + N)というようにおけば牛ゲーになる。

牛ゲー不等式に変換したら、そのグラフを作る。
iからjに辺があるとき最短距離はd[j]≦d[i] + e[i][j]を満たすので、
要するに上の式だとjからiにconstの辺を張ればいい。

このグラフに負のループがなければ制約を満たす解が存在する。
Bellman-Fordのアルゴリズムを使えばO(VE)とかなので間に合う。

なんか間に合わなかったので更新がなくなるかループ検出したら即終了としたら間に合った。

#define F first
#define S second
 
const int N = 1000;
int n, m, p[N], q[N], zero;
ll dist[2 * N + 1];
vector<pair<pi, int> > es;
 
int main(){
	scanf("%d%d", &n, &m);
	zero = 2 * n;
	
	rep(i, n){
		scanf("%d", p + i);
		es.pb(mp(mp(zero, i), p[i]));
		es.pb(mp(mp(i, zero), 0));
	}
	rep(i, n){
		scanf("%d", q + i);
		es.pb(mp(mp(i + n, zero), q[i]));
		es.pb(mp(mp(zero, i + n), 0));
	}
	rep(i, m){
		int x, y, a, b;
		scanf("%d%d%d%d", &x, &y, &a, &b);
		x--; y--;
		es.pb(mp(mp(y + n, x), b));
		es.pb(mp(mp(x, y + n), -a));
	}
	rep(i, 2 * n) dist[i] = inf;
	
	rep(it, 2 * n + 2){
		bool update = 0;
		
		rep(i, es.size()){
			int a = es[i].F.F, b = es[i].F.S, c = es[i].S;
			if(dist[a] < inf && dist[b] > dist[a] + c){
				dist[b] = dist[a] + c;
				update = 1;
				if(it == 2 * n + 1){
					cout << "no" << endl;
					return 0;
				}
			}
		}
		if(dist[0] < 0){
			cout << "no" << endl;
			return 0;
		}
		if(!update) break;
	}
	
	rep(i, 2 * n + 1) cerr<<dist[i]<<endl;
	
	cout << "yes" << endl;
	
	return 0;
}