HDU 6041.I Curse Myself 无向仙人掌图

时间：2022-05-04 23:05:56

I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2266    Accepted Submission(s): 544

Problem 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 (∑k=1Kk⋅V(k))mod232.

 
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≤106), 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≤105).

 
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
 
Source
 
Recommend
liuyiding   |   We have carefully selected several similar problems for you:  6216 6215 6214 6213 6212 
 
题意：有一个n个结点，m条无向边的仙人掌图。求删除一些边形成生成树，求前k小生成树。
思路：因为是一个仙人掌图，所以每条边最多在一个简单环内。所以只需要删除每个简单环内的一条边就能形成生成树。
代码： 
#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<bitset>

using namespace std;

#define PI acos(-1.0)

#define eps 1e-8

typedef long long ll;

typedef pair<int,int> P;

const int N=1e3+,M=4e3+;

struct edge

{

    int from,to;

    int w;

    int next;

};

int n,m,k;

edge es[M];

int cnt,head[N];

int dfs_clock=;

int pre[N],low[N];

stack<int>s;

void init(int n)

{

    cnt=;

    dfs_clock=;

    for(int i=; i<=n+; i++) head[i]=-,pre[i]=;

}

void addedge(int u,int v,int w)

{

    cnt++;

    es[cnt].from=u,es[cnt].to=v;

    es[cnt].w=w;

    es[cnt].next=head[u];

    head[u]=cnt;

}

int tmp[],ans[];

struct node

{

    int num;

    int id;

    bool operator <(const node x) const

    {

        return x.num>num;

    }

};

void unit(priority_queue<node> &q)

{

    tmp[]=;

    while(tmp[]<k&&!q.empty())

    {

        node x=q.top();

        q.pop();

        tmp[++tmp[]]=x.num;

        if(++x.id<=ans[]) q.push((node)

        {

            x.num-ans[x.id-]+ans[x.id],x.id

        });

    }

    ans[]=;

    for(int i=; i<=tmp[]; i++) ans[++ans[]]=tmp[i];

}

bool dfs(int u,int fa)

{

    pre[u]=low[u]=++dfs_clock;

    for(int i=head[u]; i!=-; i=es[i].next)

    {

        int v=es[i].to;

        if(v==fa) continue;

        if(!pre[v])

        {

            s.push(i);

            dfs(v,u);

            low[u]=min(low[u],low[v]);

            if(low[v]>=pre[u])

            {

                priority_queue<node>q;

                while(!s.empty())

                {

                    int poi=s.top();

                    s.pop();

                    q.push((node){ans[]+es[poi].w,});

                    if(poi==i) break;

                }

                if(q.size()>) unit(q);

            }

        }

        else if(pre[v]<pre[u]&&v!=fa)

        {

            s.push(i);

            low[u]=min(low[u],pre[v]);

        }

    }

}

int main()

{

    int Case=;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        init(n);

        int all=;

        for(int i=; i<=m; i++)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            all+=w;

            addedge(u,v,w),addedge(v,u,w);

        }

        scanf("%d",&k);

        ans[]=,ans[++ans[]]=;

        dfs(,);

        ll sum=,mod=(1LL<<);

        for(int i=; i<=ans[]; i++)

            sum=(sum+(1LL*(all-ans[i])*i)%mod)%mod;

        printf("Case #%d: %lld\n",++Case,sum);

    }

    return ;

}

无向仙人掌图

相关文章