SPOJ 104 Highways 最小生成樹計數
來源：程序員人生 發布時間：2014-11-12 08:48:47 閱讀次數：2815次
題目鏈接：點擊打開鏈接
題意：
給定n個點m條邊的無向圖，問最小生成樹有幾個。
思路：
模版
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?⑴:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
const int N = 15;
ll a[N][N],g[N][N];
void add(int u, int v){
u--; v--;
g[u][v] = g[v][u] = 1;
}
ll DET(int n){ //點標從[0, n)
for(int i=0, u;i<n;i++)
{
u=0;
for(int j=0;j<n;j++) if(g[i][j]) u++,a[i][j]=⑴;
a[i][i]=u;
}
ll temp=1,t;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++) while(a[j][i])
{
t=a[i][i]/a[j][i];
for(int k=i;k<n;k++)
a[i][k]-=a[j][k]*t;
for(int k=i;k<n;k++)
{
t=a[i][k];
a[i][k]=a[j][k];
a[j][k]=t;
}
temp=-temp;
}
temp=temp*a[i][i];
}
if(temp<0) temp=-temp;
return temp;
}
void init(){
memset(a,0,sizeof(a));
memset(g,0,sizeof(g));
}
int n, m;
int main(){
int T, u, v; rd(T);
while(T--){
rd(n); rd(m);
init();
while(m--){
rd(u); rd(v);
add(u,v);
}
pt(DET(n)); putchar('
');
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
