UVa-11157 : Dynamic Frog
問題概要
幅Dの川がある。途中には大きな石と小さな石がある。小さな石は1回乗ると壊れる。意志を中継して川を往復したい。利用する石の間隔の最大値の最小値を求める問題。
解法
二分探索+最大流。小さい石は対応する頂点に容量制限を付け加える。INFをあまり大きくしないよう注意。
acceptされたコード
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 100; const int MAX_V = 2*MAX_N + 2; int bs[MAX_N+2], ss[MAX_N]; int B, S, D; typedef int flow_t; const flow_t INF = 1<<20; const flow_t EPS = 0; struct edge{ int to, rev; flow_t cap; }; vector<edge> graph[MAX_V]; int level[MAX_V]; int iter[MAX_V]; void add_edge(int from, int to, flow_t cap){ graph[from].push_back((edge){to,(int)graph[to].size(), cap}); graph[to].push_back((edge){from,(int)graph[from].size()-1, 0}); } void bfs(int source){ memset(level, -1, sizeof(level)); queue<int> que; level[source] = 0; que.push(source); while(!que.empty()){ int v = que.front(); que.pop(); for(int i=0; i<(int)graph[v].size(); i++){ edge &e = graph[v][i]; if(e.cap > 0 && level[e.to] < 0){ level[e.to] = level[v] + 1; que.push(e.to); } } } } flow_t dfs(int v, int sink, flow_t f){ if(v == sink){ return f; } for(int &i = iter[v]; i <(int)graph[v].size(); i++){ edge &e = graph[v][i]; if(e.cap > EPS && level[v] < level[e.to]){ int d = dfs(e.to, sink, min(f, e.cap)); if(d > EPS){ e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } flow_t max_flow(int source, int sink){ flow_t flow = 0; for(;;){ bfs(source); if(level[sink] < 0){ break; } memset(iter, 0, sizeof(iter)); flow_t f; while((f = dfs(source, sink, INF)) > 0){ flow += f; } } return flow; } void init(){ B = S = 0; int N; scanf("%d%d ", &N, &D); for(int i=0; i<N; i++){ char c; int d; scanf("%c-%d ", &c, &d); if(c == 'B'){ bs[B++] = d; } else{ ss[S++] = d; } } bs[B++] = 0; bs[B++] = D; } bool check(int x){ for(int i=0; i<MAX_V; i++){ graph[i].clear(); } const int source = B + 2*S - 2, sink = source + 1; for(int i=0; i<S; i++){ add_edge(i, i+S, 1); add_edge(i+S, i, 1); } for(int i=0; i<S; i++){ for(int j=i+1; j<S; j++)if(abs(ss[i] - ss[j]) <= x){ add_edge(i+S, j, INF); add_edge(j+S, i, INF); } } for(int i=0; i<S; i++){ for(int j=0; j<B; j++)if(abs(ss[i] - bs[j]) <= x){ add_edge(i+S, j+2*S, INF); add_edge(j+2*S, i, INF); } } for(int i=0; i<B; i++){ for(int j=i+1; j<B; j++)if(abs(bs[i] - bs[j]) <= x){ add_edge(i+2*S, j+2*S, INF); add_edge(j+2*S, i+2*S, INF); } } return max_flow(source, sink) >= 2; } int solve(){ int low = 0, high = D; while(high - low > 1){ int mid = (high + low) / 2; if(check(mid)){ high = mid; } else{ low = mid; } } return high; } int main(){ int T; scanf("%d", &T); for(int c=1; c<=T; c++){ init(); printf("Case %d: %d\n", c, solve()); } return 0; }