最小生成树，然后看他有多少个连通分量，每个连通分量有个飞机场，最后看所有剩下的边是否有大于飞机场的费用，有的话，改成飞机场；
比赛的时候一直没想明白，╮(╯▽╰)╭；
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define maxn 100009 5 using namespace std; 6 int n,m,a; 7 struct edge 8 { 9 int u,v,w; 10 bool operator<(const edge& t)const 11 { 12 return w<t.w; 13 } 14 }ed[maxn]; 15 int f[10009],pen[10009],ans,cnt; 16 int find(int x) 17 { 18 return x==f[x]?x:f[x]=find(f[x]); 19 } 20 21 bool kruskal() 22 { 23 for(int i=0;i<m;i++) 24 { 25 int x=find(ed[i].u); 26 int y=find(ed[i].v); 27 if(x!=y) 28 { 29 f[x]=y; 30 pen[cnt++]=ed[i].w; 31 ans+=ed[i].w; 32 } 33 } 34 } 35 36 int main() 37 { 38 int ca=1,num,t; 39 scanf("%d",&t); 40 while(t--) 41 { 42 scanf("%d%d%d",&n,&m,&a); 43 ans=num=cnt=0; 44 memset(pen,0,sizeof pen); 45 for(int i=1;i<=n;i++)f[i]=i; 46 for(int i=0;i<m;i++) 47 scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w); 48 sort(ed,ed+m); 49 kruskal(); 50 for(int i=1;i<=n;i++)if(i==find(i))num++; 51 for(int i=0;i<=cnt;i++) 52 if(pen[i]>=a) 53 { 54 num++; 55 ans-=pen[i]; 56 } 57 ans+=num*a; 58 printf("Case #%d: %d %d ",ca++,ans,num); 59 } 60 return 0; 61 }