时间管理大师(
查看原帖
时间管理大师(
356081
Night_7d5楼主2020/12/13 12:18

求助,全TLE

#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int x=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') {
			w=-1;
			c=getchar();
		}
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*w;
}
const int N=1e3+1,M=1e5+1;
struct edge {
	int u,v,w;
}E[M];
inline int cmp(edge a,edge b) {
	return (a.w<b.w)?1:0;
}
int parent[N];
inline void build(int n) {
	for(int i=1;i<=n;i++) {
		parent[i]=i;
	}
}
inline int find(int k) {
	if(k!=parent[k]) {
		parent[k]=find(parent[k]);
	}
	return parent[k];
}
inline void Union(int a,int b) {
	parent[find(a)]=find(b);
}
int main()
{
    int n,m,k;
	n=read();m=read();k=read();	
	for(int i=1;i<=m;i++) {
		E[i].u=read();E[i].v=read();E[i].w=read();
	}
	sort(E+1,E+m+1,cmp);
	build(n);
	int ans=0,t=0;
	for(int i=1;i<=m;i++) {
		if(find(E[i].u)!=find(E[i].v)) {
			Union(E[i].u,E[i].v);
			ans+=E[i].w;
			++t;
		}
		if(t==n-k) {
			printf("%d",t);
			return 0;
		}
	}
	printf("No Answer");
	return 0;
}
2020/12/13 12:18
加载中...