http://acm.cs.ecnu.edu.cn/problem.php?problemid=2165
找了個(gè)次小生成樹的題目做一做。
方法是先找出最小生成樹，然后依次添加每條在原圖中，而不在MST上的邊，然后刪除
形成的環(huán)上的最大邊（先通過dfs預(yù)處理求出MST上任意點(diǎn)之間的最大邊權(quán)），這樣
形成了一棵新樹，找出所有添加刪除形成的secondary minimum spanning tree就OK了！
#include <stdio.h>
#include<string.h>
#define INF 2139062143
int m,n,min_dif,flag,lowcost[501],map[501][501],mst_map[501][501],
s[501],pre[501],max_val[501][501],vis[501];
void dfs(int sta,int t,int max){
for(int i=1;i<=n;i++){
if(!vis[i] && mst_map[t][i]!=INF){
vis[i]=1;
int tmp=max;
if(mst_map[t][i]>max) max=mst_map[t][i];
if(max>max_val[sta][i]) max_val[sta][i]=max_val[i][sta]=max;
dfs(sta,i,max);
max=tmp;
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(map,127,sizeof(map));
memset(mst_map,127,sizeof(mst_map));
memset(lowcost,127,sizeof(lowcost));
memset(s,0,sizeof(s));
memset(pre,0,sizeof(pre));
memset(max_val,128,sizeof(max_val));
int i,j,idx,min_mst=0,mincost,a,b,c;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
}
//prim algorithm
lowcost[1]=0;
for(i=1;i<=n;i++){
mincost=INF;
for(j=1;j<=n;j++)
if(!s[j] && lowcost[j]<mincost){
mincost=lowcost[j];
idx=j;
}
s[idx]=1;
min_mst+=mincost;
mst_map[idx][pre[idx]]=mst_map[pre[idx]][idx]=map[pre[idx]][idx];
for(j=1;j<=n;j++){
if(!s[j] && map[idx][j]<lowcost[j]){
lowcost[j]=map[idx][j];
pre[j]=idx;
}
}
}
//calc max_val[i][j]
for(i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
vis[i]=1;
dfs(i,i,-INF);
}
//for each edge excluded int the MST
//try to get secondary minimum spanning tree
min_dif=INF;flag=0;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(mst_map[i][j]==INF && map[i][j]!=INF){
flag=1;//mark if there's s new tree
if(map[i][j]-max_val[i][j]<min_dif) min_dif=map[i][j]-max_val[i][j];
}
}
}
if(!flag) printf("%d -1\n",min_mst);
else printf("%d %d\n",min_mst,min_mst+min_dif);
}
return 0;
}