C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 432K, 提交时间: 2020-07-24 14:39:00

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=55,inf=0x3f3f3f3f;
int n,m,f[N];
struct node{int u,v,w;}t[N*N];
struct SW{
	int g[N][N],vis[N],d[N],com[N],s,t,mi;
	void init(){memset(g,0,sizeof g);}
	void prim(){
		memset(vis,0,sizeof vis);	memset(d,0,sizeof d); s=t=-1;	int id;
		for(int i=1;i<=n;i++){
			int mx=-inf;
			for(int j=1;j<=n;j++)	if(!com[j]&&!vis[j]&&d[j]>mx)	id=j,mx=d[j];
			if(t==id)	return ;
			s=t; t=id;	mi=mx;	vis[id]=1;
			for(int j=1;j<=n;j++)	if(!com[j]&&!vis[j])	d[j]+=g[id][j];
		}
	}
	int calc(){
		memset(com,0,sizeof com); int res=inf;
		for(int i=1;i<n;i++){
			prim();
			if(mi<res)	res=mi;	
			if(res==0)	return 0;
			com[t]=1;
			for(int j=1;j<=n;j++) if(!com[j]) g[s][j]+=g[t][j],g[j][s]+=g[j][t];
		}
		return res;
	}
}sw;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void solve(){
	sw.init();
	for(int i=1;i<=n;i++)	f[i]=i;
	for(int i=1;i<=m;i++)	scanf("%d %d %d",&t[i].u,&t[i].v,&t[i].w);
	sort(t+1,t+1+m,[](node a,node b){return a.w<b.w;});
	for(int i=1,j=1;i<=m;i++){
		j=i;
		while(t[j].w==t[j+1].w)	j++;
		for(int k=i;k<=j;k++) if(find(t[k].u)!=find(t[k].v)){
			sw.g[t[k].u][t[k].v]++,sw.g[t[k].v][t[k].u]++;
		}
		for(int k=i;k<=j;k++) f[find(t[k].u)]=find(t[k].v);
		i=j;
	}
	printf("%d\n",sw.calc());
}
signed main(){
	while(cin>>n>>m)	solve();
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 376K, 提交时间: 2020-10-12 09:30:44

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int>vv[55];
int main()
{
    int n,m,u,v,num;
    while(cin >> n >> m){
        while(m--){
            cin >> u >>v >> num;
            vv[u].push_back(num);
            vv[v].push_back(num);
        }
        int ans = 550000 ;
        for(int i=1;i<=n;i++){
            sort(vv[i].begin(),vv[i].end());
            //out << vv[i][0] << endl;
            ans = min(ans,(int)(upper_bound(vv[i].begin(),vv[i].end(),vv[i][0])-vv[i].begin()));
            vv[i].clear();
        }
        cout << ans <<endl;
    }
    return 0;
}