P1955程序自动分析求纠错
查看原帖
P1955程序自动分析求纠错
441359
Fighting_For_211楼主2022/11/15 16:21

P1955程序自动分析为啥样例都过0分 我下载的第一组不过的数据在我编译器也是完全正确的 我不理解呀

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=200010;
int p[N];
vector<int> alls;
int s[N];

struct Node{
	int a,b,e;
}A[N];

int FIND(int x) 
{
	int l=0,r=alls.size()-1;
	while(l<r)
	{
		int mid=l+r>>1;
		if(alls[mid]>=x) r=mid;
		else
		l=mid+1;
	}//cout<<"PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP";
	return r;
}

int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

void merge(int a,int b)
{
	p[find(a)]=find(b);
	return;
}

bool cmp(Node a,Node b)
{
	return a.e>b.e;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int k=1;k<=n;k++) /////////////
		{
			int i,j,e;
			cin>>i>>j>>e;
			alls.push_back(i);
			alls.push_back(j);	
			A[k]={i,j,e};	
		}
		
		sort(alls.begin(),alls.end());
		alls.erase(unique(alls.begin(),alls.end()),alls.end());
		
		sort(A+1,A+n+1,cmp);///////////////
		
		bool flag=true;
		
		for(int i=1;i<=n;i++)
		{
			int ee=A[i].e;
			int a=FIND(A[i].a);
			int b=FIND(A[i].b);
			if(ee)
			{
				if(find(a)!=find(b))
				merge(a,b);
			}
			else
			{
				if(find(a)==find(b))
				flag=false;
				cout<<"No";
				if(t>1)
				cout<<endl; 
			}
		}	
		if(flag)
		{
			cout<<"Yes";
			if(t>1)
			cout<<endl;
		}
		
		 
	}
}
2022/11/15 16:21
加载中...