bzoj1016 [JSOI2008]最小生成樹計數

1016: [JSOI2008]最小生成樹計數

Time Limit:?1 Sec??Memory Limit:?162 MB
Submit:?6032??Solved:?2452
[Submit][Status][Discuss]

Description

　　現在給出了一個簡單無向加權圖。你不滿足于求出這個圖的最小生成樹，而希望知道這個圖中有多少個不同的
最小生成樹。（如果兩顆最小生成樹中至少有一條邊不同，則這兩個最小生成樹就是不同的）。由于不同的最小生
成樹可能很多，所以你只需要輸出方案數對31011的模就可以了。

Input

　　第一行包含兩個數，n和m，其中1<=n<=100; 1<=m<=1000; 表示該無向圖的節點數和邊數。每個節點用1~n的整
數編號。接下來的m行，每行包含兩個整數：a, b, c，表示節點a, b之間的邊的權值為c，其中1<=c<=1,000,000,0
00。數據保證不會出現自回邊和重邊。注意：具有相同權值的邊不會超過10條。

Output

　　輸出不同的最小生成樹有多少個。你只需要輸出數量對31011的模就可以了。

Sample Input

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

Sample Output

8

分析：這道題還是比較坑的......首先我們要利用一條性質：一個圖的所有的最小生成樹的同一邊權的邊的數目是相等的，也就是說：我們如果把最小生成樹上的邊權排序，那么所有最小生成樹的排列都是一樣的。這個要怎么證明呢？為了簡便起見，我們假設有2個不同的邊權x1,x2，x1<x2,如果x1有2個，x2有2個，另一個最小生成樹x1有3個，x2有1個，那么這是不可能的，因為第二個最小生成樹的邊權和已經比第一個的小了，如果第二個最小生成樹x1有1個，x2有3個，這也不是最小生成樹，以此類推，就能證明這個性質（可能不是完全正確的，但是明白這個結論就好了）。

???? 知道這個結論就比較好處理了。我們接下來要做的就是枚舉每個邊權滿足要求的邊數，這里滿足的要求是fa[x] != fa[y],也就是構成最小生成樹的要求，因為有這個限制，所以不能用組合數，于是我們用dfs,看到了最后是不是達到了我們一開始求的那個最小生成樹的邊權的邊的數目。也就是說：我們以第一個最小生成樹為模板，后面的生成樹的邊權數與第一個相等的邊的數目必須相等，同時檢測是不是滿足要求就可以了。

???? 有一個坑點：這個圖可能不能成為一棵樹......

?????還有一個坑點：并查集不能用路徑壓縮，不然dfs不好還原.

???? 還有一個要注意的地方：我們枚舉完一個邊權的邊后，要把這些邊全部連起來，為什么呢，因為這為以后判斷下一個邊權的邊是否滿足條件奠定基礎.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int mod = 31011;int n, m, fa[1100],cnt,tot,l[1100],r[1100],sum[1100],ans = 1;struct node
{int a, b, c;
}e[1010];bool cmp(node a, node b)
{return a.c < b.c;
}int find1(int x)
{if (x == fa[x])return x;return find1(fa[x]);
}int dfs(int x,int y,int z)
{int res = 0;if (y == r[x] + 1){if (z == sum[x])return 1;return 0;}int fx = find1(e[y].a), fy = find1(e[y].b);if (fx != fy){fa[fx] = fy;res += dfs(x, y + 1, z + 1);res %= mod;fa[fx] = fx;}res += dfs(x, y + 1, z);res %= mod;return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)fa[i] = i;for (int i = 1; i <= m; i++)scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);sort(e + 1, e + 1 + m, cmp);for (int i = 1; i <= m; i++){if (i == 1)l[++cnt] = 1;elseif (e[i].c != e[i - 1].c){r[cnt] = i - 1;l[++cnt] = i;}int fx = find1(e[i].a), fy = find1(e[i].b);if (fx != fy){fa[fx] = fy;tot++;sum[cnt]++;}}r[cnt] = m;if (tot != n - 1){printf("0\n");return 0;}for (int i = 1; i <= n; i++)fa[i] = i;for (int i = 1; i <= cnt; i++){int tmp = dfs(i,l[i],0);ans = (ans * tmp) % mod;for (int j = l[i]; j <= r[i]; j++){int fx = find1(e[j].a), fy = find1(e[j].b);if (fx != fy)fa[fx] = fy;}}printf("%d\n", ans % mod);return 0;
}

?