生成树的计数(基尔霍夫矩阵)：UVAoj 10766 Organising the Organisation SPOJ HIGH

HIGH - Highways

 

　　In some countries building highways takes a lot of time... Maybe that's because there are many possiblities to construct a network of highways and engineers can't make up their minds which one to choose. Suppose we have a list of cities that can be connected directly. Your task is to count how many ways there are to build such a network that between every two cities there exists exactly one path. Two networks differ if there are two cities that are connected directly in the first case and aren't in the second case. At most one highway connects two cities. No highway connects a city to itself. Highways are two-way.

Input

　　The input begins with the integer t, the number of test cases (equal to about 1000). Then t test cases follow. The first line of each test case contains two integers, the number of cities (1<=n<=12) and the number of direct connections between them. Each next line contains two integers a and b, which are numbers of cities that can be connected. Cities are numbered from 1 to n. Consecutive test cases are separated with one blank line.

Output

　　The number of ways to build the network, for every test case in a separate line. Assume that when there is only one city, the answer should be 1. The answer will fit in a signed 64-bit integer.

Example

Sample input:
4
4 5
3 4
4 2
2 3
1 2
1 3

2 1
2 1

1 0

3 3
1 2
2 3
3 1

Sample output:
8
1
1
3

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=20;
int C[maxn][maxn],n,m;

int Solve(){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++)
            while(C[j][i]){
                int r=C[i][i]/C[j][i];
                for(int k=i;k<n;k++)
                    C[i][k]-=C[j][k]*r;
                swap(C[i],C[j]);    
            }
    }
    long long ret=1;
    for(int i=1;i<n;i++)    
        ret*=C[i][i];
    return ret<0?-ret:ret;        
} 

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(C,0,sizeof(C));
        scanf("%d%d",&n,&m);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            C[a][a]++;C[b][b]++;
            C[a][b]=C[b][a]=-1;
        }
        printf("%d
",Solve());
    }
    return 0;
}

10766 - Organising the Organisation

Time limit: 3.000 seconds

Input: Standard Input

Output: Standard Output

Time Limit: 2 Second

　　I am the chief of the Personnel Division of a moderate-sized company that wishes to remain anonymous, and I am currently facing a small problem for which I need a skilled programmer's help.

　　Currently, our company is divided into several more or less independent divisions. In order to make our business more efficient, these need to be organised in a hierarchy, indicating which divisions are in charge of other divisions. For instance, if there are four divisions A, B, C and D we could organise them as in Figure 1, with division A controlling divisions B and D, and division D controlling division C.

　　One of the divisions is Central Management (division A in the figure above), and should of course be at the top of the hierarchy, but the relative importance of the remaining divisions is not determined, so in Figure 1 above, division C and D could equally well have switched places so that C was in charge over division D. One complication, however, is that it may be impossible to get some divisions to cooperate with each other, and in such a case, neither of these divisions can be directly in charge of the other. For instance, if in the example above A and D are unable to cooperate, Figure 1 is not a valid way to organise the company.

　　In general, there can of course be many different ways to organise the organisation, and thus it is desirable to find the best one (for instance, it is not a good idea to let the programming people be in charge of the marketing people). This job, however, is way too complicated for you, and your job is simply to help us find out how much to pay the consultant that we hire to find the best organisation for us. In order to determine the consultant's pay, we need to find out exactly how difficult the task is, which is why you have to count exactly how many different ways there are to organise the organisation.

Oh, and I need the answer in five hours.

Input

　　The input consists of a series of test cases, at most 50, terminated by end-of-file. Each test cases begins with three integers n, m, k (1 ≤ n ≤ 50, 0 ≤ m ≤ 1500, 1 ≤ k ≤ n). ndenotes the number of divisions in the company (for convenience, the divisions are numbered from 1 to n), and k indicates which division is the Central Management division. This is followed by m lines, each containing two integers 1 ≤ i, j ≤ n, indicating that division i and division j cannot cooperate (thus, i cannot be directly in charge of j and jcannot be directly in charge of i). You may assume that i and j are always different.

Output

　　For each test case, print the number of possible ways to organise the company on a line by itself. This number will be at least 1 and at most 1015.

Sample Input Output for Sample Input

5 5 2 3 1 3 4 4 5 1 4 5 3 4 1 1 1 4 3 0 2

3 8 3

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=53;
int n,m,rt,G[maxn][maxn];
long long C[maxn][maxn];
long long Solve(){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++)
            while(C[j][i]){
                long long r=C[i][i]/C[j][i];
                for(int k=i;k<n;k++)    
                    C[i][k]-=C[j][k]*r;
                swap(C[i],C[j]);    
            }
    }
    long long ret=1;
    for(int i=1;i<n;i++)
        ret*=C[i][i];
    return ret<0?-ret:ret;
}
int main(){
    while(scanf("%d%d%d",&n,&m,&rt)==3){
        memset(G,-1,sizeof(G));
        memset(C,0,sizeof(C));
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            G[a][b]=G[b][a]=0;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&G[i][j]){
                    C[i][j]=-1;
                    C[i][i]+=1;
                }
        printf("%lld
",Solve());            
    }
    return 0;
}