题解：UVA10766 Organising the Organisation

IcyDragon · 2026-08-07 14:40:49 · 题解

思路

比较板的矩阵树定理，先用 map 记录下素有不兼容关系对，然后暴力建完全图，若为在 map 中有记录的不兼容关系对则不建边。

既然题目已经给定了中央管理部门的编号，那么我们就去除第 k 行和第 k 列即可（当然去除的行列不是 k 也不会错，因为这是无向图）。

代码

#include<iostream>
#include<map>
using namespace std;

typedef long long lld;
map<pair<int,int>,int> mp;
lld a[110][110],d[110][110];

void solve(int n,int m,int _k){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = d[i][j] = 0;
        }
    }
    mp.clear();
    int x,y;
    for(int i = 1; i <= m; i++){
        cin>>x>>y;
        mp[{x,y}] = mp[{y,x}] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(mp[{i,j}]){
                continue;
            }
            a[i][j]++,
            d[j][j]++;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = d[i][j]-a[i][j];
        }
    }
    lld ans = 1;
    int p;
    auto abs = [](lld x){
        return x<0 ? -x : x;
    };
    for(int i = 1; i <= n; i++){
        if(i == _k){
            continue;
        }
        p = -1;
        for(int j = i; j <= n; j++){
            if(j == _k){
                continue;
            }
            if(a[j][i]){
                p = j;
            }
        }
        if(p == -1){
            ans = 0;
            break;
        }
        if(p != i){
            for(int j = 1; j <= n; j++){
                if(j == _k){
                    continue;
                }
                swap(a[p][j],a[i][j]);
            }
            ans = -ans;
        }
        for(int j = i+1; j <= n; j++){
            if(j == _k){
                continue;
            }
            while(a[j][i]){
                if(abs(a[i][i]) < abs(a[j][i])){
                    for(int k = 1; k <= n; k++){
                        if(k == _k){
                            continue;
                        }
                        swap(a[i][k],a[j][k]);
                    }
                    ans = -ans;
                }else{
                    lld _ = a[i][i]/a[j][i];
                    for(int k = i; k <= n; k++){
                        if(k == _k){
                            continue;
                        }
                        a[i][k] -= _*a[j][k];
                    }
                }
            }
        }
        ans *= a[i][i];
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m,k;
    while(cin>>n>>m>>k){
        solve(n,m,k);
    }
    return 0;
}