【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6041
【题目大意】
给出一个仙人掌图，求第k小生成树
【题解】
首先找到仙人掌图上的环，现在的问题就是从每个环中删除一个元素，
求出删除元素总和中的第K大，我们发现通过限定第K大的大小，可以有效地搜索剪枝，
限制的大小导致搜索出来的总和数量是具有单调性的，我们可以二分这个值，
然后用搜索来定位第K大的大小。Thanks to Claris。
【代码】
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1010,M=2010,ALL=100010;
vector<int> v[N],w[N],a[N];
int Cas=1,n,m,K,st[N],pos,base,ans[ALL],dfn,f[N],fw[N],L,R,MID,t,cnt;
unsigned Ans;
bool cmpd(int x,int y){return x>y;}
bool cmp(const vector<int>&a,const vector<int>&b){return a[1]<b[1];}
void dfs(int x){
//printf("%d
",x);
st[x]=++dfn;
for(int i=0;i<v[x].size();i++){
int y=v[x][i],z=w[x][i];
if(y==f[x])continue;
if(!st[y]){f[y]=x;fw[y]=z;dfs(y);}
else if(st[y]<st[x]){
a[cnt].push_back(z);
for(int j=x;j!=y;j=f[j])a[cnt].push_back(fw[j]);
sort(a[cnt].begin(),a[cnt].end(),cmpd);
base-=a[cnt][0];
for(int j=a[cnt].size()-1;~j;j--)a[cnt][j]=a[cnt][0]-a[cnt][j];
cnt++;
}
}
}
void dfs2(int x,int s){
if(pos>=K||x==cnt)return;
if(s+a[x][1]>MID)return;
for(int i=1;i<a[x].size();i++){
int sum=s+a[x][i];
if(sum>MID)break;
if(pos>=K)return;
ans[++pos]=sum;
dfs2(x+1,sum);
}dfs2(x+1,s);
}
int cal(){
LL ans=1;
for(int i=0;i<cnt;i++){
ans*=a[i].size();
if(ans>1000000)return 1000000;
}return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
v[x].push_back(y); v[y].push_back(x);
w[x].push_back(z); w[y].push_back(z);
base+=z;
}dfs(1);
sort(a,a+cnt,cmp);
scanf("%d",&K);
K=min(K,cal());
L=0,R=1000000000;
while(L<=R){
MID=(L+R)>>1; pos=1;
dfs2(0,0);
if(pos>=K)R=(t=MID)-1;
else L=MID+1;
}MID=t-1;
pos=0;
if(MID>=0)ans[++pos]=0;
dfs2(0,0);
for(int i=pos+1;i<=K;i++)ans[i]=t;
sort(ans+1,ans+K+1);
for(int i=1;i<=K;i++){
ans[i]+=base;
Ans+=1U*ans[i]*i;
}printf("Case #%d: %u
",Cas++,Ans);
for(int i=1;i<=n;i++)f[i]=fw[i]=st[i]=0;
for(int i=0;i<cnt;i++)a[i].clear();
for(int i=1;i<=n;i++)v[i].clear(),w[i].clear();
dfn=base=Ans=cnt=0;
}return 0;
}