1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int n,m,k,tot,MST=0,fa[2010]; 7 #define maxm 10000 8 struct Edge{ 9     int to,value,from;10     bool operator < (const Edge &a ) const{11         return value<a.value;12     }13 }e[maxm*2+10];14 void Add_Edge(int u,int v,int w){15     e[++tot].to=v;e[tot].value=http://www.mamicode.com/w;e[tot].from=u;16 }17 int Find(int x){18     if(x==fa[x])return x;19     else return fa[x]=Find(fa[x]);20 }21 int main()22 {23     24     scanf("%d%d%d",&n,&m,&k);25     for(int i=1,u,v,w;i<=m;i++){26         scanf("%d%d%d",&u,&v,&w);27         Add_Edge(u,v,w);28     }29     if(n<k){30         printf("No Answer\n");31         return 0;32     }33     sort(e+1,e+tot+1);34     for(int i=1;i<=n+10;i++) fa[i]=i;35     int cur=0;36     for(int i=1;i;i++){37         int v=e[i].to,u=e[i].from;38         int rx=Find(u),ry=Find(v);39         if(rx!=ry){40             cur++;41             MST+=e[i].value;42             fa[rx]=ry;43         }44         if(cur == n-k )break;45     }46     printf("%d",MST);47     return 0;48 }49 /*思路 ：取 前K条边  连成一棵最小生成树 50 其余的单独成树51 */

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,k,ans,fa[1111]; 7 struct node{ 8     int from; 9     int to;10     int value;11     bool operator <(const node &a)const 12     {13         return value<a.value;14     }15 }Edge[11111];16 int find(int x)17 {18     if(x==fa[x]) return x;19     else return fa[x]=find(fa[x]);20 }21 int main()22 {23     cin>>n>>m>>k;24     int x,y,l;25     for(int i=1;i<=m;i++)26     {27         cin>>x>>y>>l;28         Edge[i].from=x;29         Edge[i].to=y;30         Edge[i].value=http://www.mamicode.com/l;31     }32     33     for(int i=1;i<=n;i++)34       fa[i]=i;35       36      sort(Edge+1,Edge+m+1); 37     38     int js=1,h=1;39     // js 是当前已用边数40     // 此题是个最小生成树问题  需成多棵树 41     // h 用于记录排好序的边中 用到了第几条 42     if((k>n)||((n-k)>m))//  (n-k)k棵最小生成树 需要的边数 然而只有m条边so~~ 43     {44         printf("No Answer\n");45         return 0;46     } 47     while(js<=n-k)// 生成一棵树用n-1条边，k棵则需要n-k条边 48     {49         50         int rx=Edge[h].from;51         int ry=Edge[h].to;52         int w=Edge[h].value;53         int fx=find(rx);int fy=find(ry);54         if(fx!=fy)55         {56             js++;57             fa[fx]=fy;58             ans+=w;59         }60         h++;61     }62     63      printf("%d\n",ans);64     65     return 0;66 }