http://acm.timus.ru/problem.aspx?space=1&num=1416
又是次小生成树啊。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 #define maxn 505 6 #define inf (int)(1<<31-1) 7 int s[maxn][maxn],f[maxn][maxn],lowcost[maxn],closest[maxn],flag; 8 void init(int n) 9 { 10 for(int i=1;i<=n;i++) 11 for(int j=1;j<=n;j++){ 12 f[i][j]=-inf; 13 s[i][j]=inf; 14 } 15 } 16 int mst(int n) 17 { 18 int k,ans=0; 19 for(int i=1;i<=n;i++){ 20 lowcost[i]=s[1][i]; 21 closest[i]=1; 22 } 23 lowcost[1]=-1; 24 for(int i=1;i<n;i++){ 25 int min=inf; 26 for(int j=1;j<=n;j++) 27 if(lowcost[j]!=-1&&min>lowcost[j]){ 28 min=lowcost[j]; 29 k=j; 30 } 31 if(min==inf) 32 flag=1; 33 ans+=min; 34 //printf("%d** ",ans); 35 for(int j=1;j<=n;j++) 36 if(lowcost[j]==-1){ 37 f[j][k]=max(f[j][closest[k]],lowcost[k]); 38 f[k][j]=f[j][k]; 39 } 40 lowcost[k]=-1; 41 s[closest[k]][k]=inf; 42 s[k][closest[k]]=inf; 43 for(int j=1;j<=n;j++) 44 if(lowcost[j]!=-1&&lowcost[j]>s[k][j]){ 45 lowcost[j]=s[k][j]; 46 closest[j]=k; 47 } 48 } 49 return ans; 50 } 51 int deal(int n) 52 { 53 int ans=inf; 54 for(int i=1;i<=n;i++) 55 for(int j=1;j<=n;j++) 56 if(s[i][j]!=inf) 57 ans=min(ans,s[i][j]-f[i][j]); 58 return ans; 59 } 60 int main() 61 { 62 int n,m; 63 while(~scanf("%d%d",&n,&m)){ 64 init(n); 65 while(m--){ 66 int a,b,c; 67 scanf("%d%d%d",&a,&b,&c); 68 s[a][b]=c; 69 s[b][a]=c; 70 } 71 flag=0; 72 int ans=mst(n); 73 if(flag==1){ 74 printf("Cost: -1 Cost: -1 "); 75 continue; 76 } 77 int s1=deal(n); 78 if(s1==inf){ 79 printf("Cost: %d Cost: -1 ",ans); 80 } 81 else 82 printf("Cost: %d Cost: %d ",ans,ans+s1); 83 } 84 return 0; 85 }