生活随笔
收集整理的這篇文章主要介紹了
[JSOI2008]最小生成树计数
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?
OJ題號：
BZOJ1016
題目大意：
給定一個無向帶權圖，求最小生成樹的個數。
思路：
先跑一遍最小生成樹，統計相同權值的邊出現的個數。
易證不同的最小生成樹，它們不同的那一部分邊的權值實際上是相同的。
所以我們可以暴力枚舉相同權值的邊，統計加入這些邊總共能有多少種方法。
根據乘法原理，把每種邊的方法數乘起來即可。
然后就O(2^n)暴力水過這道題。
實際上用Matrix-Tree可以做到O(n^3)。
1 */
2 #include<cstdio>
3 #include<cctype>
4 #include<vector>
5 #include<algorithm>
6
7 inline
int getint() {
8 register
char ch;
9 while(!isdigit(ch=
getchar()));
10 register
int x=ch^
'0';
11 while(isdigit(ch=getchar())) x=(((x<<
2)+x)<<
1)+(ch^
'0');
12 return x;
13 }
14 const int mod=
31011;
15 const int V=
101;
16
17 struct Edge1 {
18 int u,v,w;
19 bool operator < (
const Edge1 &another)
const {
20 return w<
another.w;
21 }
22 };
23 std::vector<Edge1>
e1;
24
25 struct Edge {
26 int to,w;
27 };
28 std::vector<Edge>
e[V];
29 inline
void add_edge(
const int &u,
const int &v,
const int &
w) {
30 e[u].push_back((Edge){v,w});
31 }
32
33 struct DisjointSet {
34 int anc[V],cnt;
35 int find(
const int &x)
const {
36 return x==anc[x]?
x:find(anc[x]);
37 }
38 void reset(
const int &
n) {
39 cnt=
n;
40 for(register
int i=
1;i<=n;i++
) {
41 anc[i]=
i;
42 }
43 }
44 void Union(
const int &x,
const int &
y) {
45 anc[find(x)]=
find(y);
46 cnt--
;
47 }
48 bool isConnected(
const int &x,
const int &y)
const {
49 return find(x)==
find(y);
50 }
51 int stat()
const {
52 return cnt;
53 }
54 };
55 DisjointSet s;
56
57 struct Hash {
58 unsigned l,r;
59 int v;
60 };
61 std::vector<Hash>
a;
62
63 inline
void kruskal() {
64 std::sort(e1.begin(),e1.end());
65 for(register unsigned i=
0;i<e1.size();i++
) {
66 if(!
i) {
67 a.push_back((Hash){
0,
0,
0});
68 }
else if(e1[i].w!=e1[i-
1].w) {
69 a.back().r=i-
1;
70 a.push_back((Hash){i,
0,
0});
71 }
72 const int &u=e1[i].u,&v=e1[i].v,&w=
e1[i].w;
73 if(s.isConnected(u,v))
continue;
74 s.Union(u,v);
75 add_edge(u,v,w);
76 add_edge(v,u,w);
77 a.back().v++
;
78 }
79 a.back().r=e1.size()-
1;
80 }
81
82 int tmp;
83 void dfs(
const int &
in,
const unsigned x,
const int d) {
84 if(x>a[
in].r) {
85 if(d==a[
in].v) tmp++
;
86 return;
87 }
88 const int &u=e1[x].u,&v=
e1[x].v;
89 const int p=s.find(u),q=
s.find(v);
90 if(p!=
q) {
91 s.anc[p]=
q;
92 dfs(
in,x+
1,d+
1);
93 s.anc[p]=
p;
94 s.anc[q]=
q;
95 }
96 dfs(
in,x+
1,d);
97 }
98
99 int main() {
100 int n=
getint();
101 for(register
int m=getint();m;m--
) {
102 const int u=getint(),v=getint(),w=
getint();
103 e1.push_back((Edge1){u,v,w});
104 }
105 s.reset(n);
106 kruskal();
107 if(s.stat()!=
1) {
108 puts(
"0");
109 return 0;
110 }
111 s.reset(n);
112 int ans=
1;
113 for(register unsigned i=
0;i<a.size();i++
) {
114 tmp=
0;
115 dfs(i,a[i].l,
0);
116 ans=(ans*tmp)%
mod;
117 for(register unsigned j=a[i].l;j<=a[i].r;j++
) {
118 const int &u=e1[j].u,&v=
e1[j].v;
119 if(s.isConnected(u,v))
continue;
120 s.Union(u,v);
121 }
122 }
123 printf(
"%d\n",ans);
124 return 0;
125 }
?
轉載于:https://www.cnblogs.com/skylee03/p/7575427.html
總結
以上是生活随笔為你收集整理的[JSOI2008]最小生成树计数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
