这个是次小生成树，我用的是n^2的算法，先算出最小生成树，然后算出每一条路径中最大的边，然后枚举每一条不再树上的边。。
代码写的巨丑。。悲剧囧。
Code：
#include<cstdio>#include<vector>#include<algorithm>#include<iostream>#define all(x) x.begin(),x.end()using namespace std;typedef pair<int,int> ii;typedef pair<int,ii> Edge;typedef vector<ii> vii;typedef vii::iterator vit;typedef vector<vii> vvii;vector<Edge> E,NotOnTree;vector<int> F;const int maxn=500;int n,m;void setF(){ for(int i=0;i<n;i++)F.push_back(i);}int Find(int x){ if(x==F[x]) return x; return F[x]=Find(F[x]);}void Union(int a,int b){ F[b]=a;}void Init(){ scanf("%d %d",&n,&m);int s,t,c; while(m–) { scanf("%d %d %d",&s,&t,&c);–s;–t; E.push_back(Edge(c,ii(s,t))); }}vii edge[maxn];int Total=0;void Ins_Edge(int s,int t,int c){ edge[s].push_back(ii(t,c)); edge[t].push_back(ii(s,c));}void dealEdge(const Edge&e){ ii t=e.second; int i=Find(t.first),j=Find(t.second); if(i!=j) { Union(i,j); Ins_Edge(t.first,t.second,e.first); Total+=e.first; } else { NotOnTree.push_back(e); }}void CalMST(){ sort(all(E)); setF(); for_each(all(E),dealEdge);}int Max_Edge[maxn][maxn];int s;void dfs(int x,int f,int Max){ Max_Edge[s][x]=Max; for(vit e=edge[x].begin();e!=edge[x].end();++e) if(e->first!=f) dfs(e->first,x,max(Max,e->second));}int Ans;void dealEdge2(const Edge&e){ int Now=Total-Max_Edge[e.second.first][e.second.second]+e.first; //cout<<e.second.first<<" "<<e.second.second<<" "<<e.first<<endl; //cout<<Now<<endl; if(Ans==-1||Now<Ans) Ans=Now;}void Work(){ CalMST();Ans=-1; for(int i=0;i<n;i++)s=i,dfs(i,-1,0); for_each(all(NotOnTree),dealEdge2); cout<<"Cost:"<<Total<<endl; cout<<"Cost:"<<Ans<<endl;}int main(){ //freopen("in","r",stdin); Init(); Work();}