LOJ#505. 「LibreOJ β Round」ZQC 的游戏(最大流)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意

题目链接

Sol

首先把第一个人能吃掉的食物删掉

然后对每个人预处理出能吃到的食物，直接限流跑最大流就行了

判断一下最后的最大流是否等于重量和

注意一个非常恶心的地方是需要把除1外所有人都吃不到的食物删掉

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
int sqr(int x) {return x * x;}
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, S, T, deep[MAXN], cur[MAXN], vis[MAXN];
struct Edge {
int u, v, f, nxt;
}E[MAXN];
int head[MAXN], num;
void add_edge(int x, int y, int f) {E[num] = (Edge) {x, y, f, head[x]}; head[x] = num++;}
inline void AddEdge(int x, int y, int f) {add_edge(x, y, f); add_edge(y, x, 0);}
int x[MAXN], y[MAXN], w[MAXN], r[MAXN], fx[MAXN], fy[MAXN], fw[MAXN], flag[MAXN];
void init() {
S = 0; T = 233333; num = 0;
memset(vis, 0, sizeof(vis));
memset(head, -1, sizeof(head));
memset(flag, 0, sizeof(flag));
}
bool check(int a, int b) {return (sqr(x[a] - fx[b]) + sqr(y[a] - fy[b]) <= sqr(r[a]));}
bool BFS() {
queue<int>q; q.push(S);
memset(deep, 0, sizeof(deep));
deep[S] = 1;
while(q.size() != 0) {
int p = q.front(); q.pop();
for(int i = head[p]; i != -1; i = E[i].nxt) {
if(E[i].f && !deep[E[i].v]) {
deep[E[i].v] = deep[p] + 1;
if(E[i].v == T) return deep[T];
q.push(E[i].v);
}
}
}
return deep[T];
}
int DFS(int x, int flow) {
if(x == T) return flow;
int ansflow = 0;
for(int &i = cur[x]; i != -1; i = E[i].nxt) {
if(deep[E[i].v] == deep[x] + 1 && E[i].f) {
int canflow = DFS(E[i].v, min(E[i].f, flow));
flow -= canflow;
E[i].f -= canflow; E[i ^ 1].f += canflow;
ansflow += canflow;
if(flow <= 0) break;
}
}
return ansflow;
}
int Dinic() {
int ans = 0;
while(BFS()) {
memcpy(cur, head, sizeof(head));
ans += DFS(S, INF);
}
return ans;
}
void solve() {
init();
N = read(); M = read();
for(int i = 1; i <= N; i++) x[i] = read(), y[i] = read(), w[i] = read(), r[i] = read();
for(int i = 1; i <= M; i++) fx[i] = read(), fy[i] = read(), fw[i] = read();
int Lim = w[1], ned = 0;
for(int i = 1; i <= M; i++)
if(check(1, i)) Lim += fw[i], flag[i] = 1;
else ned += fw[i];
for(int i = 2; i <= N; i++) {
AddEdge(S, i, Lim - w[i]);///还能再吃这些食物
if(Lim - w[i] <= 0) {puts("qaq"); return ;}
for(int j = 1; j <= M; j++)
if(!flag[j] && check(i, j)) AddEdge(i, j + N, INF), vis[j] = 1;
}
for(int i = 1; i <= M; i++) {
if(!flag[i]) AddEdge(i + N, T, fw[i]);
if(!vis[i]) ned -= fw[i];//谁都吃不到
}
puts(Dinic() >= ned ? "ZQC! ZQC!" : "qaq");
}
signed main() {
for(int T = read(); T; T--, solve());
return 0;
}
/*
2
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 4
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 5
*/