这段代码为什么能AC?(含反抄袭)
查看原帖
这段代码为什么能AC?(含反抄袭)
1598749
sera_him楼主2024/11/28 17:08

含反抄袭,复制无法AC含反抄袭,复制无法AC

#include <bits/stdc++.h>
#define O s2[i]
using namespace std;
int trans[501],x[501],y[501],r[501],s[501],n,ans,s1[501],s2[501],que[5001];
bool arr[501],table[501][501];
bool atob(int a,int b)
{
	if (a==b)
	    return false;
	if (r[a]*r[a]>=(x[a]-y[a])*(x[a]-y[a])+(x[b]-y[b])*(x[b]-y[b]))
	    return true;
	return false;
}
void greed(int x)
{
	if (arr[x])
	    return;
	arr[x]=true;
	s1[x]=s[x];
	for (int i=1;i<=n;i++)
	    if (i==trans[i] && atob[x][i] && !arr[i])
	    {
	    	greed(i);
	    	s1[x]+=s1[i];
	    	s2[x]+=max(O,s2[i]);
		}
	s2[x]=max(s1[x],s2[x]);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
	    scanf("%d%d%d%d",x+i,y+i,r+i,s+i);
	    trans[i]=i;
	    que[i]=i;
	}
	for (int i=1;i<=n;i++)
	    for (int j=1;j<=n;j++)
		    table[i][j]=atob(i,j);
	for (int L=1,R=n;L<=R;L++)
	{
	    for (int i=1;i<=n;i++)
	        if (table[que[L]][i])
	            for (int j=1;j<=n;j++)
	                if (i!=j && !table[que[L]][j] && table[i][j])
	                {
	                	table[L][j]=true;
	                	if (!arr[i])
	                	{
	                	    que[R++]=i;
	                	    arr[i]=true;
	                	}
					}
		arr[que[L]]=false;
	}
	for (int i=1;i<=n;i++)
	    if (i==trans[i])
	        for (int j=i+1;j<=n;j++)
	            if (table[i][j] && table[j][i])
	            {
	                trans[j]=i;
	                s[i]+=s[j];
	            }
	for (int i=1;i<=n;i++)
	    if (i==trans[i] && !arr[i])
	    {
	    	greed(i);
	        ans+=max(s1[i],s2[i]);
	    }
	printf("%d",ans);
}
2024/11/28 17:08
加载中...