裸的最小生成树。
code:
/************************************************************** Problem: 1083 User: yekehe Language: C++ Result: Accepted Time:24 ms Memory:2012 kb ****************************************************************/ #include <cstdio> #include <algorithm> using namespace std; char tc() { static char fl[100000],*A=fl,*B=fl; return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } int read() { char c;while(c=tc(),(c<'0'||c>'9')&&c!='-'); int x=0,y=1;c=='-'?y=-1:x=c-'0'; while(c=tc(),c>='0'&&c<='9')x=x*10+c-'0'; return x*y; } const int MAXN=305; int N,M,a[MAXN],fa[MAXN],ans; struct node{ int x,y,c; }L[MAXN*MAXN]; int cmp(node x,node y){return x.c<y.c;} int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} int main() { // freopen("x.txt","r",stdin); N=read(),M=read(); for(int i=1;i<=M;i++)L[i].x=read(),L[i].y=read(),L[i].c=read(); sort(L+1,L+M+1,cmp); for(int i=1;i<=N;i++)fa[i]=i; for(int i=1;i<=M;i++){ int x=getf(L[i].x),y=getf(L[i].y),c=L[i].c; if(x!=y){ fa[x]=y; ans=c; } } printf("%d %d",N-1,ans); return 0; }