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