题目：
点这里OvO http://acm.hdu.edu.cn/showproblem.php?pid=6041
2017 Multi-University Training Contest - Team 1 - 1009
题解：
1.由于每条边只在一个环中，每个环必然要拿掉一条边，而这些边都是不重复的，那么最小生成树就对应的是通过求每个环中拿掉一条边，总和最大的组合对应的剩下的树（第k小生成树对应第k大组合剩下的树）。xjbdfs搜一下环，把每个环中的点放到一个集合中。
2.然后对集合排序，xjb利用优先队列 ( 要注意优先队列中的元素的数量要保持和新集合的元素个数相同,以降低时间复杂度 ) 求最大的k（如果总数没k个那就不是k个）个组合（每个集合中取一个元素的组合）
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 #include <queue> 8 9 using namespace std; 10 11 typedef long long ll; 12 13 const int N=1e4+55; 14 const int M=2e3+44; 15 const ll mod=(ll)pow(2,32); 16 17 struct node{ 18 int u,v,d; 19 int next; 20 }edge[2*N]; 21 22 struct NODE 23 { 24 int v,now; //value is (v), now add with (now) 25 friend bool operator<(NODE x,NODE y) 26 { 27 return x.v < y.v; 28 } 29 };//small to big 30 31 priority_queue<NODE> Q; 32 int num; 33 int head[N]; 34 int n,m,k; 35 ll ans; 36 int snum; 37 int stk[N],lstk; 38 bool instk[M]; 39 vector<int> s[N]; 40 int val[M][M]; 41 vector<int> f,tmpf; 42 ll sum_of_edge; 43 ll du[M]; 44 45 bool cmp(int a,int b) 46 { 47 return a>b; 48 } 49 50 void addedge(int u,int v,int d) 51 { 52 edge[num].u=u; 53 edge[num].v=v; 54 edge[num].d=d; 55 edge[num].next=head[u]; 56 head[u]=num++; 57 } 58 59 void init() 60 { 61 num=0; //记得初始化 62 memset (head,-1,sizeof(head)); 63 memset(du,0,sizeof(du)); 64 snum=0; 65 lstk=0; 66 memset(instk,0,(n+4)*sizeof(bool)); 67 for(int i=1;i<=n;i++) 68 s[i].clear(); 69 ans=0; 70 sum_of_edge=0; 71 } 72 73 void dfs(int rt,int fa) 74 { 75 int v; 76 if(instk[rt]) 77 { 78 snum++; 79 int sav=rt; 80 int sav_lstk=lstk; 81 while(stk[lstk]!=rt) 82 { 83 s[snum].push_back(val[sav][stk[lstk]]); 84 sav=stk[lstk--]; 85 } 86 s[snum].push_back(val[sav][stk[lstk]]); 87 lstk=sav_lstk; 88 return ; 89 } 90 instk[rt]=1; 91 stk[++lstk]=rt; 92 for(int i=head[rt];i!=-1;i=edge[i].next) 93 { 94 v=edge[i].v; 95 if(v==fa || du[v]==0) continue; 96 du[rt]--; du[v]--; 97 dfs(v,rt); 98 } 99 instk[rt]=0; 100 lstk--; 101 } 102 103 void merge() 104 { 105 NODE q; 106 int i,j,cnt; 107 f.clear(); 108 if(snum==0) 109 { 110 f.push_back(0); 111 return ; 112 } 113 for(int i=0;i<s[1].size();i++) 114 f.push_back(s[1][i]); 115 for(int i=2;i<=snum;i++) 116 { 117 cnt=f.size()*s[i].size(); 118 if(cnt>k) cnt=k; 119 while(!Q.empty()) 120 Q.pop(); 121 for(j=0;j<s[i].size();j++) 122 { 123 q.v=s[i][j]+f[0]; 124 q.now=0; 125 Q.push(q); 126 } 127 tmpf.clear(); 128 while(cnt--) 129 { 130 q=Q.top(); 131 Q.pop(); 132 tmpf.push_back(q.v); 133 if(q.now!=f.size()-1) 134 { 135 q.v-=f[q.now]; 136 q.now++; 137 q.v+=f[q.now]; 138 Q.push(q); 139 } 140 } 141 swap(f,tmpf); 142 } 143 // cout<<"check merge "; 144 // for(int i=0;i<f.size();i++) 145 // printf("%d ",f[i]); 146 // printf(" "); 147 // printf("end of check of merge "); 148 } 149 150 void solve() 151 { 152 dfs(1,-1); 153 for(int i=1;i<=snum;i++) 154 sort(s[i].begin(),s[i].end(),cmp); 155 // printf("check s "); 156 // for(int i=1;i<=snum;i++) 157 // { 158 // for(int j=0;j<s[i].size();j++) 159 // printf("%d",s[i][j]); 160 // printf(" "); 161 // } 162 // printf("end of check of s "); 163 merge(); 164 } 165 166 int main() 167 { 168 int cas=0,a,b,c; 169 while(scanf("%d%d",&n,&m)!=EOF) 170 { 171 init(); 172 for(int i=1;i<=m;i++) 173 { 174 scanf("%d%d%d",&a,&b,&c); 175 addedge(a,b,c); 176 addedge(b,a,c); 177 du[a]++; du[b]++; 178 val[a][b]=val[b][a]=c; 179 sum_of_edge+=c; 180 } 181 scanf("%d",&k); 182 solve(); 183 for(int i=0;i<f.size();i++) 184 ans=(ans+1ll*(i+1)*(sum_of_edge-f[i])%mod)%mod; 185 printf("Case #%d: %lld ",++cas,ans%mod); 186 } 187 return 0; 188 }