c/c++语言开发共享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 */