首页 > 代码库 > hdu 4896 Minimal Spanning Tree

hdu 4896 Minimal Spanning Tree

2024-07-15 06:33:41   218人阅读

Minimal Spanning Tree

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 144    Accepted Submission(s): 44


Problem Description
Given a connected, undirected, weight graph G, your task is to select a subset of edges so that after deleting all the other edges, the graph G is still connected. If there are multiple ways to do this, you should choose the way that minimize the sum of the weight of these selected edges.

Please note that the graph G might be very large. we‘ll give you two numbers: N, and seed, N is number of nodes in graph G, the following psuedo-code shows how to to generate graph G.



Here ⊕ represents bitwise xor (exclusive-or).
 

 

Input
Input contains several test cases, please process till EOF.
For each test case, the only line contains two numbers: N and seed.(1 ≤ N ≤ 10000000, 1 ≤ seed ≤ 2333332)
 

 

Output
For each test case output one number, the minimal sum of weight of the edges you selected.
 

 

Sample Input
6 2877
2 17886
3 22452
 

 

Sample Output
2157810
259637
1352144
 

 

Author
Fudan University
 
我们打表发现x的周期是54，然后又发现边的权值周期也是54，我们就去暴力生成树权值的增量，会发现ans[i]-ans[i-54] 
在i 》 某个值是是成立的，这样我们暴力前108个，然后按周期增量处理
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#define maxn 10010#define mod 2333333#define LL long longusing namespace std;struct node{    int u,v,val ;    bool operator<(const node&s) const    {        return val < s.val ;    }}qe[maxn];int fa[maxn] ;LL ans[maxn] ;int find(int x ){    if(x != fa[x])        fa[x] = find(fa[x]) ;    return fa[x] ;}LL get(int n ){    LL ans = 0 ;    sort(qe,qe+n) ;    for(int i = 0 ; i < n ;i++ )    {        int u = find(qe[i].u) ;        int v = find(qe[i].v) ;        if(u==v) continue ;        ans += qe[i].val ;        fa[u] = v ;    }    return ans ;}int main(){    int i ,k,j ;    int x , n , m ;    while( scanf("%d%d",&n,&x ) != EOF )    {        m  = 0 ;        for( i = 2 ; i <= 108 ;i++)        {            x = x*907%mod ;            int T = x ;            for(int j = 1 ; j <= i ;j++)                fa[j]=j;            for( j = max(1,i-5) ; j <= i-1 ;j++ )            {                x = 907*x%mod ;                int w = T^x ;                qe[m].u=i;                qe[m].v=j;                qe[m++].val=w ;            }            ans[i] = get(m) ;           // if(i > 108) cout << ans[i]-ans[i-54] << endl;        }        if(n <= 108) cout << ans[n] << endl;        else        {            cout << ans[54+n%54]+(n/54-1)*(ans[108]-ans[54])<< endl ;        }    }    return 0 ;}

　　

 


联系
我们