TopCoder SRM438 Div1Hard
問題
ある国の軍隊は、いくつかのミサイルサイロを持っていて、ミサイルサイロから敵国の基地へ向かってミサイルを撃とうとしている。各サイロは、ミサイルを撃っても発射されるまでにある時間がかかる。また、ミサイルを発射したら次のミサイルを撃つまでに時間がかかる。ミサイルは敵の基地へ向かって一定の速度で進む。全ての基地を攻撃するためにかかる時間の最小値を求めよ。
解答
二分探索して、最大流やるだけ
コード
#include <vector> #include <queue> #include <algorithm> #include <cmath> #include <ctime> class dinic { /* for every edge (src, dest, cap, flow), it must have pair edge (dest, src, 0, -flow) */ struct edge { edge *next, *pair; int src, dest, cap, flow; }; int v, e; edge *pool, **con; int top; int* level; public: dinic(int _v, int _e) { v = _v; e = _e; pool = new edge[e]; con = new edge*[v]; for(int i=0;i<v;i++) con[i] = NULL; top = 0; } ~dinic() { delete [] pool; delete [] con; } edge* _add_edge(int src, int dest, int cap) { edge* ed = &(pool[top++]); ed->src = src; ed->dest = dest; ed->cap = cap; ed->flow = 0; ed->next = con[src]; con[src] = ed; return ed; } void add_pair(int src, int dest, int cap1, int cap2) { edge *e1 = _add_edge(src, dest, cap1); edge *e2 = _add_edge(dest, src, cap2); e1->pair = e2; e2->pair = e1; } int dfs(int s, int d, int cap) { if(s==d || cap==0) return cap; int w = 0; for(edge* ed = con[s]; ed != NULL; ed = ed->next) if(level[ed->dest] > level[s]){ int f = dfs(ed->dest, d, std::min(cap - w, ed->cap - ed->flow)); if(f > 0){ ed->flow += f; ed->pair->flow -= f; w += f; } } return w; } long long max_flow(int s, int d) { level = new int[v]; for(int i=0;i<e;i++) pool[i].flow = 0; long long ret = 0; for(bool update=true; update; ){ update = false; //derminate distance std::fill(level, level+v, -1); level[s] = 0; std::queue<int> q; q.push(0); int ps; while(!q.empty()){ ps = q.front(); q.pop(); for(edge* ed = con[ps]; ed != NULL; ed = ed->next){ if(ed->cap > ed->flow && level[ed->dest]==-1){ level[ed->dest] = level[ps] + 1; q.push(ed->dest); } } } for(;;){ int gain = dfs(s, d, 0x7FFFFFFF); if(gain==0) break; ret += gain; update = true; } } delete [] level; return ret; } }; using namespace std; class FeudaliasWar { vector<int> bX, bY, sX, sY; double takeOff, recharge, missile; double dist(int X, int Y) { return sqrt((double)X*X+(double)Y*Y); } bool test(double t) { int edge = bX.size() * sX.size() + bX.size(); for(int i=0;i<bX.size();i++){ for(int j=0;j<sX.size();j++){ for(int k=0;k<bX.size();k++){ double req = dist(bX[k]-sX[j], bY[k]-sY[j]) / missile + takeOff*(i+1) + recharge*i; if(req <= t) edge++; } } } dinic dn(bX.size() * sX.size() + bX.size() + 2, edge*2); for(int i=0;i<bX.size();i++){ dn.add_pair(0, i+bX.size()*sX.size()+2, 1, 0); for(int j=0;j<sX.size();j++){ dn.add_pair(i*sX.size()+j+2, 1, 1, 0); for(int k=0;k<bX.size();k++){ double req = dist(bX[k]-sX[j], bY[k]-sY[j]) / missile + takeOff*(i+1) + recharge*i; if(req <= t){ dn.add_pair(k+bX.size()*sX.size()+2, i*sX.size()+j+2, 1, 0); } } } } int tmp = dn.max_flow(0, 1); //printf("%f %d\n", t, tmp); return tmp == bX.size(); } public: double getMinimumTime(vector<int> baseX, vector<int> baseY, vector<int> siloX, vector<int> siloY, int takeOffTime, int rechargeTime, int missileSpeed) { bX = baseX; bY = baseY; sX = siloX; sY = siloY; takeOff = takeOffTime / 60.0; recharge = rechargeTime; missile = missileSpeed; clock_t t1 = clock(), t2; double left=0.0, right=1e8; for(int i=0;;i++){ t2 = clock(); if(t2 - t1 >= 1.9 * CLOCKS_PER_SEC) break; if(right-left<1e-9) break; double mid = (left+right)/2; if(test(mid)){ right = mid; }else{ left = mid; } } return left; } };