首页 > 代码库 > hdu 4896 Minimal Spanning Tree
hdu 4896 Minimal Spanning Tree
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).
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)
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 ;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。