网站版建设,系统开发是做什么的,上海企业网站建设方法,儿童不宜的广告前言
这题题意描述不是很清楚啊#xff0c;所以我找了个有权限的人把题面改了改#xff0c;应该还是比较清楚了。
感觉这道题挺妙的#xff0c;就来写一篇题解。
思路
首先#xff0c;根据贪心思想#xff0c;我们会将 1 1 1 号点半径以内能吃的都吃了#xff0c;假…前言
这题题意描述不是很清楚啊所以我找了个有权限的人把题面改了改应该还是比较清楚了。
感觉这道题挺妙的就来写一篇题解。
思路
首先根据贪心思想我们会将 1 1 1 号点半径以内能吃的都吃了假设吃完之后它的重量为 s u m sum sum。
那么为了让它成为最大的第 i i i 个人吃的重量必须满足 e a t i ≤ s u m − w i eat_i \le sum-w_i eati≤sum−wi。
那么既然如此我们就可以考虑建一个网络对于第 i i i 个人将他与他半径以内能吃的东西连一条容量为极大值的边随便找一个入点 s s s 和汇点 t t t。显然对于第 i i i 个人 s s s 就向他连一条容量为 s u m − w i sum-w_i sum−wi 的边显然如果更大那么第一个点就不是最大的了并对于任意一个球向汇点连一条边容量为 w i w_i wi每个吃的只能被吃一次。由于每个能吃的球必须被吃完所以必须要保证这个网络的最大流是满流即最大流等于网络中每个球的重量之和否则球就吃不完不满足题意故第一个节点也就成不了最大的重量。
注意事项有些球对于所有的人他都吃不到要自动忽略这些点。
代码
#includebits/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[maxe1];
int fst[maxn],cnt1;
void adds(int x,int y,long long z)
{arr[cnt].tary,arr[cnt].nxtfst[x],fst[x]cnt,arr[cnt].numz;
}
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));queueint p;p.push(t);dis[t]0;now[t]fst[t];gap[0]1;while(!p.empty()){int xp.front();p.pop();for(int ifst[x];i;iarr[i].nxt){int jarr[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(xt){flowsum;return sum;}long long l0;for(int inow[x];i;iarr[i].nxt){now[x]i;int jarr[i].tar;long long karr[i].num;if(k0dis[j]dis[x]-1){long long useddfs(j,min(k,sum-l));if(used){arr[i].num-used;arr[i^1].numused;lused;}if(lsum) return l;}}--gap[dis[x]];if(!gap[dis[x]]) dis[s]n1;dis[x];gap[dis[x]];return l;}int output(){flow0;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));cnt1;memset(fst,0,sizeof(fst));//初始化scanf(%d%d,n,m);setint pqr;//储存那些节点没有被遍历到long long sum0,leftsum0;//sum表示总和leftans表示网络中球的重量之和for(int i1;in;i) scanf(%d%d%d%d,nx[i],ny[i],nw[i],r[i]);for(int i1;im;i) scanf(%d%d%d,x[i],y[i],w[i]),pqr.insert(i);snm1,tnm2;//入点和汇点sumnw[1];for(int i1;im;i){if(dis(nx[1],ny[1],x[i],y[i])r[1]){pqr.erase(pqr.find(i));vis[i]true;sumw[i];}}for(int i2;in;i) for(int j1;jm;j) if(dis(nx[i],ny[i],x[j],y[j])r[i]) if(pqr.count(j)) pqr.erase(pqr.find(j));for(int i2;in;i){if(sum-nw[i]0)//如果已经不行了那就自动忽略{puts(qaq);return;}adds(s,i,sum-nw[i]),adds(i,s,0);//入点和人连边}for(int i2;in;i){for(int j1;jm;j){if(dis(nx[i],ny[i],x[j],y[j])r[i])adds(i,jn,0x3f3f3f3f3f3f3f3f),adds(jn,i,0);//人与球连边}}for(int i1;im;i) if((!pqr.count(i))(!vis[i])) adds(in,t,w[i]),adds(t,in,0),leftsumw[i];nnm-1;//ISAP一定要改n的值哦int shitISAP::output();
// coutshitendl;if(shitleftsum) puts(ZQC! ZQC!);else puts(qaq);
}
signed main()
{int tt;cintt;while(tt--){input();}return 0;
}
