P3324 [SDOI2015]星际战争（洛谷刷题记录）

P3324 [SDOI2015]星际战争

转洛谷网站

题解

重难点依然是建图
考虑攻击力限制条件
一个是攻击装置能够发射的伤害
一个是防御装置能够承受的伤害
建立超级源点超级汇点
源点向武器建边，边权为攻击参数
防御向汇点建边，边权为防御系数
武器与防御之间边权infinf即可
考虑二分答案
加入现在拥有一个攻击时间
那么每个武器的输出变成原来的攻击力 * 攻击时间
此时对全图跑最大流
如果最大流和防御系数之和相等
证明当前时间可以摧毁所有防御机器人
那么就可以缩小答案规模
反之当前输出不够摧毁所有机器人
那么增加答案使输出更接近防御系数之和
考虑精度问题
可以给所有防御系数乘上10000（因为精度限制只有1000）
攻击参数不动
这样跑出来的攻击时间会比原来大10000倍
再将答案除以10000输出即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define int long long
#define min(a, b) ({register int aa = a, bb = b; aa > bb ? bb : aa;})
#define inf 0x7fffffff
using namespace std;

//c的读入优化
inline int read(){
	int x = 0, w = 1;
	char ch = getchar();
	for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return x * w;
}

const int ss = 10010;

struct node{
	int to, nxt, w;
}edge[ss * 20];

int head[ss], tot = 1;
inline void add(register int u, register int v, register int w){
	edge[++tot].to = v;
	edge[tot].nxt = head[u];
	edge[tot].w = w;
	head[u] = tot;
}

int dis[ss], cur[ss];
int n, m, s, t;
bool vis[ss];
queue<int> q;
inline bool spfa(register int s){
	for(register int i = 0; i <= t; i++)
		dis[i] = 0x3f3f3f3f, cur[i] = head[i], vis[i] = 0;
	dis[s] = 0;
	q.push(s);
	while(!q.empty()){
		register int u = q.front();
		q.pop();
		vis[u] = 0;
		for(register int i = head[u]; i; i = edge[i].nxt){
			register int v = edge[i].to;
			if(dis[v] > dis[u] + 1 && edge[i].w){
				dis[v] = dis[u] + 1;
				if(!vis[v]) q.push(v), vis[v] = 1;
			}
		}
	}
	return dis[t] != 0x3f3f3f3f;
}

inline int dfs(register int u, register int flow){
	register int res = 0;
	if(u == t) return flow;
	for(register int i = cur[u]; i; i = edge[i].nxt){
		cur[u] = i;
		register int v = edge[i].to;
		if(dis[v] == dis[u] + 1 && edge[i].w){
			if(res = dfs(v, min(flow, edge[i].w))){
				edge[i].w -= res;
				edge[i ^ 1].w += res;
				return res;
			}
		}
	}
	return 0;
}

inline long long dinic(){
	register long long maxflow = 0;
	register long long minflow = 0;
	while(spfa(s)){
		while(minflow = dfs(s, 0x7fffffff))
			maxflow += minflow;
	}
	return maxflow;
}

long long a[ss], b[ss], sum;
bool map[55][55];
inline bool check(register long long x){
	for(register int j = 1; j <= m; j++)
		b[j] *= x;
	memset(head, 0, sizeof head);
	memset(cur, 0, sizeof cur);
	tot = 1;
	for(register int i = 1; i <= m; i++)
		add(s, i, b[i]), add(i, s, 0);
	for(register int j = 1; j <= n; j++)
		add(j + m, t, a[j]), add(t, j + m, 0);
	for(register int j = 1; j <= m; j++){
		for(register int i = 1; i <= n; i++){
			register bool op = map[j][i];
			if(op == 1){
				add(j, i + m, inf);
				add(i + m, j, 0);
			}
			else continue;
		}
	}
	register long long tmp = dinic();
	register bool flag = 1;
	if(tmp >= sum) flag = 1;
	else flag = 0;
	for(register int j = 1; j <= m; j++)
		b[j] /= x;
	return flag;
}

signed main(){
//读入数据
	n = read(), m = read();
	s = 0, t = n + m + 1;
	for(register int i = 1; i <= n; i++) a[i] = read() * 10000, sum += a[i];
	for(register int j = 1; j <= m; j++) b[j] = read();
	for(register int j = 1; j <= m; j++)
		for(register int i = 1; i <= n; i++)
			map[j][i] = read();
//二分			
	register long long l = 0, r = 1e9;
	while(l <= r){
		register long long mid = l + r >> 1;
		if(check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%.6lf\n", (double)l / 10000);
	return 0;
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136