同楼上四个点(6,8,12,13)错误,悬关求调
查看原帖
同楼上四个点(6,8,12,13)错误,悬关求调
560983
bai_the_fool楼主2024/5/26 16:37
#include<bits/stdc++.h>
using namespace std;
const int N=600;
struct pt{
	int x,y,id;
}city[N];
int cnt=0;
int half;
//前向星 
struct edge{
	int u,v,nxt;
}e[N*N];
int head[N]; 
void add_edge(int u,int v){
	e[++cnt]=(edge){u,v,head[u]};
	head[u]=cnt;
}
//前向星结束
 
double dis(pt a,pt b){
	int dx=abs(a.x-b.x),dy=abs(a.y-b.y); 
	return sqrt((dx*dx)+(dy*dy));
}
bool cmp(pt a,pt b){
	pt cap=(pt){0,0};
	return dis(cap,a)<dis(cap,b);
}//离首都由近到远 

int de[N];//γ值,用dfs得出 
int n;
bool vis[N];
void dfs(int x,int dep){//获取γ值 
	if(vis[x])return;
	vis[x]=1;
	de[x]=dep;
	for(int i=head[x];i;i=e[i].nxt){
		dfs(e[i].v,dep+1);
	}
}
bool dfs1(int x,int tot){//搜索判断γ值能否正好分成两份 
	if(tot>half)return 0;
	if(tot==half)return 1;
	for(int i=x+1;i<=n;i++){
		if(dfs1(i,tot+de[i]))return 1;
	}
	return 0;
}
int main(){
	cin>>n;
	city[0]=(pt){0,0,0};
	
	for(int i=1;i<=n;i++){
		cin>>city[i].x>>city[i].y;
		city[i].id=i;
	}
	
	sort(city+1,city+n+1,cmp);//排序,按照离首都远近 
	for(int i=1;i<=n;i++){
		//初始化连边选择 
		int minj=0;//选择的点 
		int minid=0;//选择点的初始编号 
		double mind=dis(city[0],city[i]);//最小距离初始化为首都与当前点的距离 
		
		for(int j=0;j<i;j++){//考虑比当前点离首都更近的 
			double disnow=dis(city[i],city[j]);
			if(disnow<mind||(disnow==mind&&city[j].id<minid)){//选择该点连边的条件:距离更小或者等距离下初始编号更小 
				mind=disnow;
				minid=city[j].id;
				minj=j;
			}
		}
		//连边 
		add_edge(i,minj);
		add_edge(minj,i);
	} 
	dfs(0,1);//从首都开始进行dfs,求出γ值 
	for(int i=0;i<=n;i++){
		half+=de[i];//累加全部γ的和 
	}
	if(half%2!=0){//如果γ不能分成两半,那么直接输出No 
		cout<<"No";
		return 0;
	}
	half/=2;//总和的一半存入half 
	if(dfs1(-1,0)){//如果能正好分成两半,输出Yes 
		cout<<"Yes";
	}
	else//否则输出No 
	{
		cout<<"No";
	}
} 
2024/5/26 16:37
加载中...