[网络流图匹配 + 二分] 导弹防御塔 CH6803

我们考虑跑 网络流 首先是 二分图最大匹配 == 入侵者数量时 时间可以缩小
点才最多50个 50 * 50 最多发 3000 不到的导弹
3000 和 原点连 3000个边
3000 和 入侵者连 最多15000边
开 前向星 按 40000 * 8 边 差不多了就 因为连的太多了
暴力点建图 将塔分成很多导弹
每个点 最多建立50个 我们预先建出来 原点到炮塔发出得导弹上
之后 按炮弹发射和冷却路上总时间 和 入侵者相连
最后 入侵者与汇点相连
我们跑最大流 如果 最大流不是 入侵者数目 r = mid 不然 l = mid

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 40000;

int n, m;
double t1, t2, v;
int s, t;
int head[10000], depth[10000], cur[10000], cnt;
int nxt[maxn << 3], to[maxn << 3], cap[maxn << 3];  

void ade(int a, int b, int c) {
	to[cnt] = b;
	cap[cnt] = c;
	nxt[cnt] = head[a];
	head[a] = cnt ++;
}

bool bfs(){
	queue<int> que;
	que.push(s);
	memset(depth, 0, sizeof(depth));
	depth[s] = 1;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i = head[u]; i != -1; i = nxt[i]) {
			if(cap[i] > 0 && depth[to[i]] == 0) {
				depth[to[i]] = depth[u] + 1;
				que.push(to[i]);
			}
		}
	}
	if(depth[t]) return 1;
	else return 0;
}

int dfs(int u, int dist) {
	if(u == t) return dist;
	for(int &i = cur[u]; i != -1; i = nxt[i]) {
		if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
			int tmp = dfs(to[i], min(dist, cap[i]));
			if(tmp > 0) {
				cap[i] -= tmp;
				cap[i ^ 1] += tmp;
				return tmp; 
			}
		}
	}
	return 0;
}

struct node{
	int x, y;
}army[55], tower[55];

int dinic() {
	int res = 0, d;
	while(bfs()) {
		for(int i = 0; i < 10000; i ++) cur[i] = head[i];
		while(d = dfs(s, INF)) res += d;
	}
	return res;
}

double getdis(node a, node b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void init(double time){
	memset(head, -1, sizeof(head));
	cnt = 0;
	for(int i = 1; i <= n; i ++) for(int j = 0; j <= m; j ++) 
			ade(s, i + j * 55, 1), ade(i + j * 55, s, 0);
	for(int i = 1; i <= n; i ++) {
		double sec;
		for(int j = 0; j < m; j ++) {
		    sec = (1.0 * t1 + 1.0 * j * (t1 + t2));
			for(int k = 1; k <= m; k ++) {
				if(sec + getdis(army[k], tower[i]) / v < time)
					ade(i + j * 55, 4000 + k, 1), ade(4000 + k, i + j * 55, 0);
			}
		}
	}
	for(int i = 1; i <= m; i ++)
		ade(4000 + i, t, 1), ade(t, 4000 + i, 0);
}

int main(){
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60;
    s = 0, t = 9000;
    for(int i = 1; i <= m; i ++) cin >> army[i].x >> army[i].y;
    for(int i = 1; i <= n; i ++) cin >> tower[i].x >> tower[i].y;
    double l = 0, r = 200000;
    while((r - l) > 1e-7) {
    	double mid = (l + r) / 2;
    	init(mid);
    	if(dinic() == m) r = mid;
    	else l = mid;
	}
	printf("%.6lf\n", r);
    return 0;
}