HDU 6041 I Curse Myself (仙人掌图)

Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.

Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define $V(k)$ as the weight of the k-th smallest weighted spanning tree of this graph, however, $V(k)$ would be defined as zero if there did not exist k different weighted spanning trees.

Please calculate $(\sum _{k=1}^Kk⋅V(k))mod~2^{32}$ .

 

Input

The input contains multiple test cases.

For each test case, the first line contains two positive integers $n,m (2≤n≤1000,n−1≤m≤2n−3)$ , the number of nodes and the number of edges of this graph.

Each of the next m lines contains three positive integers $x,y,z (1≤x,y≤n,1≤z≤10^6)$ , meaning an edge weighted z between node x and node y. There does not exist multi-edge or self-loop in this graph.

The last line contains a positive integer $K (1≤K≤10^5)$ .

 

Output

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

 

Sample Input

4 3
1 2 1
1 3 2
1 4 3
1
3 3
1 2 1
2 3 2
3 1 3
4
6 7
1 2 4
1 3 2
3 5 7
1 5 3
2 4 1
2 6 2
6 4 5
7

 

Sample Output

Case #1: 6
Case #2: 26
Case #3: 493

 

题意

求一棵无向仙人掌图中前 $k$ 小的生成树权值和。

 

思路

首先我们需要清楚什么是无向仙人掌图,它是一张连通图,且任意一条边都至多属于一个环。

也就是说,仙人掌图的一棵生成树就是其每个环去掉一条边所形成的图。

那么我们可以一次通过 $dfs$ 找出所有环,然后存储每个环中的所有边长,此时问题就变成了在 $n$ 个数组中各取一个数,求其和的前 $k$ 大的数,也算一个经典问题啦~

PS:在最后求解前 $k$ 大的和时千万不要用 $O(n^3)$ 的算法,否则 TLE 到 cry 😭

 

AC 代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 2100;
typedef pair<int,int> P;
typedef __int64 LL;

struct node
{
    int to;
    int next;
    int cost;
} edge[maxn<<1];

int head[maxn<<1],tot;
int Stack[maxn],stop;
bool instack[maxn];
int n,m,k;
bool isStart;
bool vis[maxn];
int g[maxn][maxn];
int Bcnt;
vector<int>G[maxn];
vector<int> f,tmpf;
LL mod = 1LL<<32;

void init()
{
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(instack,false,sizeof(instack));
    tot=stop=Bcnt=0;
    isStart=false;
    f.clear();
    tmpf.clear();
}

void addedge(int u,int v,int cost)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    edge[tot].cost=cost;
    head[u]=tot++;
}

void dfs(int x,int fa)
{
    Stack[++stop]=x;
    instack[x]=true;
    vis[x]=true;
    for(int i=head[x]; i!=-1; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa)continue;
        if(!vis[to])
            dfs(to,x);
        else if(instack[to])        // 找到仙人掌的一个环
        {
            vector<int> G;
            int top=stop;
            int p=to;
            while(Stack[top]!=to)   // 统计环中所有边长
            {
                G.push_back(g[p][Stack[top]]);
                p=Stack[top--];
            }
            G.push_back(g[p][Stack[top]]);
            sort(G.begin(),G.end(),[](const int &a,const int &b)    // 边长从大到小排序
            {
                return a>b;
            });
            int len=G.size();
            if(!isStart)            // 第一次计算
            {
                for(int j=0; j<len; j++)
                    f.push_back(G[j]);
                isStart=true;
            }
            else
            {
                int cnt=f.size()*len;
                cnt=min(cnt,k);
                priority_queue<P> que;
                for(int j=0; j<len; j++)
                    que.push(P(f[0]+G[j],0));
                tmpf.clear();
                while(cnt--)
                {
                    P p=que.top();
                    que.pop();
                    tmpf.push_back(p.first);
                    if(p.second!=(int)f.size()-1)
                    {
                        p.first-=f[p.second++];
                        p.first+=f[p.second];
                        que.push(p);
                    }
                }
                swap(f,tmpf);
            }
        }
    }
    instack[x]=false;
    stop--;
}

int main()
{
    for(int ti=1; ~scanf("%d%d",&n,&m); ti++)
    {
        init();
        LL cnt=0,ans=0;
        for(int i=0; i<m; i++)
        {
            int u,v,cost;
            cin>>u>>v>>cost;
            addedge(u,v,cost);
            addedge(v,u,cost);
            g[u][v]=g[v][u]=cost;
            cnt+=cost;
        }
        scanf("%d",&k);
        dfs(1,-1);
        int len=f.size();
        if(!len)ans=cnt;
        for(int i=0; i<len; i++)
            ans=(ans+(1LL*(i+1)*(cnt-f[i]))%mod)%mod;
        printf("Case #%d: %I64d\n",ti,ans);
    }
    return 0;
}