ZQC的游戏 题解

前言

这题题意描述不是很清楚啊，所以我找了个有权限的人把题面改了改，应该还是比较清楚了。

感觉这道题挺妙的，就来写一篇题解。

思路

首先，根据贪心思想，我们会将 $1$ 号点半径以内能吃的都吃了，假设吃完之后它的重量为 $sum$。

那么，为了让它成为最大的，第 $i$ 个人吃的重量必须满足 $ea{t}_i\le sum-w_i$。

那么既然如此，我们就可以考虑建一个网络，对于第 $i$ 个人，将他与他半径以内能吃的东西连一条容量为极大值的边，随便找一个入点 $s$ 和汇点 $t$。显然，对于第 $i$ 个人，$s$ 就向他连一条容量为 $sum-w_i$ 的边（显然，如果更大，那么第一个点就不是最大的了），并对于任意一个球，向汇点连一条边，容量为 $w_i$（每个吃的只能被吃一次）。由于每个能吃的球，必须被吃完，所以必须要保证这个网络的最大流是满流（即最大流等于网络中每个球的重量之和），否则，球就吃不完，不满足题意，故第一个节点也就成不了最大的重量。

注意事项：有些球对于所有的人他都吃不到，要自动忽略这些点。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 805
#define maxe 40005
int n,m,s,t;
int nx[maxn],ny[maxn],nw[maxn],r[maxn];
int x[maxn],y[maxn],w[maxn];
bool vis[maxn];
struct node
{int tar,nxt;long long num,nu2;
}arr[maxe<<1];
int fst[maxn],cnt=1;
void adds(int x,int y,long long z)
{arr[++cnt].tar=y,arr[cnt].nxt=fst[x],fst[x]=cnt,arr[cnt].num=z;
}
double dis(int x,int y,int z,int w)//求两点距离
{return sqrt((x-z)*(x-z)+(y-w)*(y-w));
}
namespace ISAP//板子
{int dis[maxn],now[maxn],gap[maxn];long long flow;void get_augmentpath(){memset(dis,0x3f,sizeof(dis));memset(now,0,sizeof(now));memset(gap,0,sizeof(gap));queue<int> p;p.push(t);dis[t]=0;now[t]=fst[t];gap[0]=1;while(!p.empty()){int x=p.front();p.pop();for(int i=fst[x];i;i=arr[i].nxt){int j=arr[i].tar;if(dis[j]==0x3f3f3f3f){p.push(j);now[j]=fst[j];dis[j]=dis[x]+1;gap[dis[j]]++;}}}return;}long long dfs(int x,long long sum){if(x==t){flow+=sum;return sum;}long long l=0;for(int i=now[x];i;i=arr[i].nxt){now[x]=i;int j=arr[i].tar;long long k=arr[i].num;if(k>0&&dis[j]==dis[x]-1){long long used=dfs(j,min(k,sum-l));if(used){arr[i].num-=used;arr[i^1].num+=used;l+=used;}if(l==sum) return l;}}--gap[dis[x]];if(!gap[dis[x]]) dis[s]=n+1;++dis[x];gap[dis[x]]++;return l;}int output(){flow=0;get_augmentpath();while(dis[s]<n) memcpy(now,fst,sizeof(now)),dfs(s,LONG_LONG_MAX);return flow;}
}
void input()
{memset(vis,0,sizeof(vis));cnt=1;memset(fst,0,sizeof(fst));//初始化scanf("%d%d",&n,&m);set<int> pqr;//储存那些节点没有被遍历到long long sum=0,leftsum=0;//sum表示总和，leftans表示网络中球的重量之和for(int i=1;i<=n;++i) scanf("%d%d%d%d",&nx[i],&ny[i],&nw[i],&r[i]);for(int i=1;i<=m;++i) scanf("%d%d%d",&x[i],&y[i],&w[i]),pqr.insert(i);s=n+m+1,t=n+m+2;//入点和汇点sum+=nw[1];for(int i=1;i<=m;++i){if(dis(nx[1],ny[1],x[i],y[i])<=r[1]){pqr.erase(pqr.find(i));vis[i]=true;sum+=w[i];}}for(int i=2;i<=n;++i) for(int j=1;j<=m;++j) if(dis(nx[i],ny[i],x[j],y[j])<=r[i]) if(pqr.count(j)) pqr.erase(pqr.find(j));for(int i=2;i<=n;++i){if(sum-nw[i]<0)//如果已经不行了，那就自动忽略{puts("qaq");return;}adds(s,i,sum-nw[i]),adds(i,s,0);//入点和人连边}for(int i=2;i<=n;++i){for(int j=1;j<=m;++j){if(dis(nx[i],ny[i],x[j],y[j])<=r[i])adds(i,j+n,0x3f3f3f3f3f3f3f3f),adds(j+n,i,0);//人与球连边}}for(int i=1;i<=m;++i) if((!pqr.count(i))&&(!vis[i])) adds(i+n,t,w[i]),adds(t,i+n,0),leftsum+=w[i];n=n+m-1;//ISAP一定要改n的值哦int shit=ISAP::output();
//	cout<<shit<<endl;if(shit==leftsum) puts("ZQC! ZQC!");else puts("qaq");
}
signed main()
{int tt;cin>>tt;while(tt--){input();}return 0;
}