1016: [JSOI2008]最小生成树计数
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3517 Solved: 1396
[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,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过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
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
HINT
Source
题意：问一个图的最小生成树有多少种
分析：
下面提供两种做法：
1、最小生成树+暴力枚举边
现象普通最小生成树一样，将边按权值排序，先做一遍最小生成树（Krus什么的），统计每种权值取得边数
显然，每种权值的边取的数量是一定的（根据最小生成树的性质，先假设前面权值的边已经取好，那现在这个权值的边每取一条，都会减少一个联通块，这样想，显然数量一定）
这样，对于每种权值的边暴力枚举每条边取不取，在尝试加入，若能加入，则这种权值的边的取法+1，最后把每种权值的边的取法乘起来
2、利用每种权值的边取的数量是一定的性质，很容易推出无论怎么加，加完某种权值的边后，图的连通性是一样的，那么，对于每种那些加完边后变成一个联通块的若干联通块，就相当于一个生成树，那么很显然可以用生成树计数
何为生成树计数（这么多天不添题就是搞这个去了，终于搞懂了）
虽然我搞懂了，但我也是看论文看懂的，有想学的自己看论文去吧
大致意思如下：
定义度数矩阵D:D[i][i]为第 i 个点的度数
定义边矩阵E：E[i][j] 为第 i 个点到第 j 个点的边的数量（边的数量也是成立的，当初我就是纠结这个，要完全搞懂生成树计数的原理才能懂哦）
定义矩阵C：C[i][j] = D[i][j] - E[i][j]
那么，生成树的数量就是矩阵C的任意一个n-1阶的主子树的行列式
行列式有一下性质：
1、将一行数每一个数乘以某一个数，加到令一行数上，行列式的结果不变
2、将任意两行调转，结果相反（符号取反）
3、上三角或下三角的行列式值为对角线的乘积
何为上三角、下三角
a1 a2 .... an
0 b2......bn
0 0 c3....cn
0 0 0 0........pn
即对角线的一边有数，另一边没数
PS：对于第二种做法，一定要判断能不能得到一棵树，不能的话，就输出 0 （卡了我好久T_T）
综上所述，本题得解
第一种
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name) {
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} const int N = , M = , Mod = ;
struct Edges {
int u, v, c; inline bool operator <(const Edges &A) const {
return c < A.c;
}
} E[M];
int n, m;
int Fa[N], U[N], Stack[N];
int Step[M], S, St[M], Ed[M];
int Ans; inline void Input() {
scanf("%d%d", &n, &m);
For(i, , m)
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].c);
} inline int Find(int x, int *P) {
int Len = ;
while(x != P[x]) {
Stack[++Len] = x;
x = P[x];
}
For(i, , Len) P[Stack[i]] = x;
return x;
} inline int Count(int State) {
int Ret = ;
while(State) {
if(State&) Ret++;
State >>= ;
}
return Ret;
} inline void Solve() {
sort(E+, E++m);
For(i, , n) Fa[i] = i; S = ;
int Last = -;
For(i, , m) {
if(Last != E[i].c) {
Ed[S] = i-;
S++, Last = E[i].c;
St[S] = i;
}
int u = Find(E[i].u, Fa), v = Find(E[i].v, Fa);
if(u == v) continue;
Fa[u] = v, Step[S]++;
}
Ed[S] = m; Ans = ;
For(i, , n) Fa[i] = i;
int Cnt, Len, Max;
bool Flag;
For(k, , S) {
if(!Step[k]) {
//printf("0\n");
continue;
}
Cnt = , Len = Ed[k]-St[k]+;
Max = <<Len;
For(State, , Max-) {
if(Count(State) != Step[k]) continue;
For(i, , n) U[i] = Fa[i];
Flag = ;
For(i, , Len-)
if((<<i)&State) {
int u = Find(E[St[k]+i].u, U),
v = Find(E[St[k]+i].v, U);
if(u == v) {
Flag = ;
break;
}
U[u] = v;
}
if(Flag) Cnt++;
} For(i, St[k], Ed[k]) {
int u = Find(E[i].u, Fa),
v = Find(E[i].v, Fa);
if(u == v) continue;
Fa[u] = v;
} //printf("%d\n", Cnt);
Ans = (Ans*Cnt)%Mod;
} For(i, , n) Fa[i] = Find(i, Fa);
For(i, , n)
if(Find(i, Fa) != Find(i-, Fa)) {
Ans = ;
break;
}
printf("%d\n", Ans);
} int main() {
SetIO("");
Input();
Solve();
return ;
}
第二种
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name) {
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} const int N = , M = , Mod = ;
struct Edges {
int u, v, c; inline bool operator <(const Edges &A) const {
return c < A.c;
}
} E[M];
int n, m;
int Fa[N], Stack[N];
int Edge[N][N], Con[N][N], Len[N];
int C[N][N];
int S, St[M], Ed[M];
bool Visit[N];
int Ans; inline void Input() {
scanf("%d%d", &n, &m);
For(i, , m)
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].c);
} inline int Find(int x) {
int Len = ;
while(x != Fa[x]) {
Stack[++Len] = x;
x = Fa[x];
}
For(i, , Len) Fa[Stack[i]] = x;
return x;
} inline int Work(int n) {
int Ret = , T;
For(i, , n) {
For(j, i+, n)
while(C[j][i]) {
T = C[i][i]/C[j][i];
For(k, i, n) {
C[i][k] -= C[j][k]*T;
swap(C[i][k], C[j][k]);
}
Ret = -Ret;
}
if(!C[i][i]) return ;
Ret = Ret*C[i][i];
}
return abs(Ret);
} inline void Solve() {
sort(E+, E++m);
For(i, , n) Fa[i] = i;
Ans = , S = ; int Last = -;
For(i, , m)
if(Last != E[i].c) {
Ed[S] = i-;
S++, Last = E[i].c;
St[S] = i;
}
Ed[S] = m; int u, v, Cnt, Now;
For(k, , S) {
For(i, , n)
For(j, , n) Edge[i][j] = ;
For(i, St[k], Ed[k]) {
u = Find(E[i].u), v = Find(E[i].v);
if(u == v) continue;
Edge[u][v]++, Edge[v][u]++;
} For(i, , n) Visit[i] = ;
For(i, St[k], Ed[k]) {
u = Find(E[i].u), v = Find(E[i].v);
if(u == v) continue;
Fa[u] = v, Visit[u] = Visit[v] = ;
} For(i, , n) Len[i] = ;
For(i, , n)
if(Visit[i]) {
u = Find(i);
Con[u][++Len[u]] = i;
} Now = ;
For(i, , n)
if(Len[i]) {
Cnt = Len[i]; For(x, , Cnt)
For(y, , Cnt) C[x][y] = ;
For(x, , Cnt)
For(y, x+, Cnt)
C[x][y] = C[y][x] = -Edge[Con[i][x]][Con[i][y]];
For(x, , Cnt)
For(j, , Cnt) C[x][x] += Edge[Con[i][x]][Con[i][j]]; Now = Now*Work(Cnt-);
} Ans = (Ans*Now)%Mod;
} For(i, , n-)
if(Find(i) != Find(i+)) {
printf("0\n");
return;
}
printf("%d\n", Ans);
} int main() {
SetIO("");
Input();
Solve();
return ;
}