HDU 6041 I Curse Myself（二分+搜索）

时间：2025-02-07 08:35:02

【题目链接】 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\n",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\n",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;

}

相关文章