UVA - 10766 Organising the Organisation（生成树计数模板）

本题的题意是给你n个人，m对人不能相互领导，k是总领导，然后给出哪m对人，问你有多少种方法。其实谁是领导无所谓的，因为这是一个无向树，这是一个关于生成树计数的模板题，代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
typedef long long LL;
const int maxn = 55;
int D[maxn][maxn];
LL C[maxn][maxn];
int n,m,k;
 
LL Det(LL a[][maxn],int n)//生成树计数:Matrix-Tree定理
{
    LL ret=1;
    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
            while(a[j][i])
            {
                LL t=a[i][i]/a[j][i];
                for(int k=i; k<n; k++)
                    a[i][k]=(a[i][k]-a[j][k]*t);
                for(int k=i; k<n; k++)
                    swap(a[i][k],a[j][k]);
                ret=-ret;
            }
        if(a[i][i]==0)
            return 0;
        ret=ret*a[i][i];
    }
    if(ret<0)
        ret=-ret;
    return ret;
}
 
int main(){
    while(cin >> n >> m >> k){
        memset(D,0,sizeof(D));
        memset(C,0,sizeof(C));
        int u,v;
        while(m--){
            scanf("%d%d",&u,&v);
            u--,v--;
            D[u][v] = D[v][u] = 1;
        }
 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j && !D[i][j]){
                    C[i][i]++;
                    C[i][j] = -1;
                }
            }
        }
 
        cout << Det(C,n) << endl;
    }
    return 0;
}

最后

以上就是平常往事为你收集整理的UVA - 10766 Organising the Organisation（生成树计数模板）的全部内容，希望文章能够帮你解决UVA - 10766 Organising the Organisation（生成树计数模板）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。