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


思路

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 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(vis,false,sizeof(vis));
memset(instack,false,sizeof(instack));
tot=stop=Bcnt=0;
isStart=false;
f.clear();
tmpf.clear();
}

{
edge[tot].to=v;
edge[tot].cost=cost;
}

void dfs(int x,int fa)
{
Stack[++stop]=x;
instack[x]=true;
vis[x]=true;
{
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;
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;
}