水一发，最小生成树。注意不连通情况。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cctype> 5 #include <algorithm> 6 #define LL unsigned __int64 7 using namespace std; 8 9 const int N= 1010; 10 const int M= 20100; 11 struct Edge{ 12 int u,v,c; 13 int next; 14 }edge[M*2]; 15 int head[N]; 16 int n,m,tot; 17 bool vis[N]; 18 int val[N]; 19 20 void addedge(int u,int v,int c){ 21 edge[tot].u=u; 22 edge[tot].v=v; 23 edge[tot].c=c; 24 edge[tot].next=head[u]; 25 head[u]=tot++; 26 } 27 28 void MST(){ 29 int u=1,v,mm,k; 30 val[u]=0; 31 for(int i=1;i<n;i++){ 32 vis[u]=true; 33 for(int e=head[u];e!=-1;e=edge[e].next){ 34 v=edge[e].v; 35 if(!vis[v]){ 36 val[v]=min(val[v],edge[e].c); 37 } 38 } 39 mm=1,k=-1; 40 for(int j=1;j<=n;j++){ 41 if(!vis[j]&&val[j]<mm){ 42 mm=val[j]; 43 k=j; 44 } 45 } 46 if(k==-1) return ; 47 u=k; 48 } 49 } 50 51 int main(){ 52 int u,v,c; 53 while(scanf("%d%d",&n,&m)!=EOF){ 54 tot=0; 55 for(int i=1;i<=n;i++){ 56 head[i]=-1; 57 vis[i]=false,val[i]=1; 58 } 59 for(int i=0;i<m;i++){ 60 scanf("%d%d%d",&u,&v,&c); 61 addedge(u,v,-c); 62 addedge(v,u,-c); 63 } 64 MST(); 65 int ans=0,i; 66 67 for(i=1;i<=n;i++){ 68 if(val[i]==1) break; 69 ans+=val[i]; 70 } 71 printf("%d ",i>n?-ans:-1); 72 } 73 return 0; 74 }