Jiufeng'sFootballTeam

There are multiple test cases, the first line contains a single integer T (1 ≤ T ≤ 3) — the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ N ≤ 2 × $10^4$ , 1 ≤ M ≤ $10^5$ ), indicating the number of people and connections.

Then followed M lines, each line contains three integers $a_i$ , $b_i$ (1 ≤ $a_i$ , $b_i$ ≤ N, $a_i$ != $b_i$ ) and $t_i$ (1 ≤ $t_i$ ≤ $10^9$ ), indicating that player $a_i$ and player $b_i$ need $t_i$ minutes of training.

C++14(g++5.4) 解法, 执行用时: 266ms, 内存消耗: 1656K, 提交时间: 2020-09-27 13:18:51

#include<bits/stdc++.h>
using namespace std;
class lu
{
	public:
		int a;
		int b;
		int jl;
};
lu sz[100005];
int f[200005];
bool cmp(lu a,lu b)
{
	return a.jl>b.jl;
}
int getf(int a)
{
	if(f[a]==a)return a;
	f[a]=getf(f[a]);
	return f[a];
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		for(int i=1;i<=a*2+1;i++)
		{
			f[i]=i;
		}
		for(int i=1;i<=b;i++)
		{
			cin>>sz[i].a>>sz[i].b>>sz[i].jl;
		}
		sort(sz+1,sz+b+1,cmp);
		int ans=0;
		for(int i=1;i<=b;i++)
		{
			int n=getf(sz[i].a);
			int m=getf(sz[i].b);
			if(n==m)
			{
				ans=sz[i].jl;
				break;
			}
			else
			{
				f[n]=getf(sz[i].b+a);
				f[m]=getf(sz[i].a+a);
			}
		}
		cout<<ans<<endl;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 100ms, 内存消耗: 1704K, 提交时间: 2020-09-26 19:19:22

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define Maxn 20005

int n,m;
int w[Maxn*2];

struct Info{
	int a,b,hp;
	bool operator < (const Info &s) const{
		return hp>s.hp;
	}
}s[maxn];

int find(int a){
	return w[a]==a?a:w[a]=find(w[a]);
}	

int main(){
    int t; scanf("%d", &t); while(t--){
	for(int i=0;i<2*Maxn;i++)
		w[i]=i;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
		scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].hp);
	sort(s,s+m);
        int re=0;
	for(int i=0;i<m;i++){
		int a=find(s[i].a),b=find(s[i].b);
		if(a==b){
            re=s[i].hp;
			break;
		}
		w[a]=find(s[i].b+n);
		w[b]=find(s[i].a+n);
	}
	printf("%d\n", re);
    }
	
	return 0;
}

详情