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

#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
*/