zkx06111's Blog

SRM 460-1 1000pts TheCitiesAndRoads

| Comments

题意

对于一个个点的图和它的一个边集,请问有多少种边集,使得那个图是基环树。

算法一

如果问题仅仅是树,只需要把原来边集产生的联通块缩成点,点权为联通块中的点数,两个点i和j的边权为w[i] * w[j],然后做一遍MatrixTree就可以了(需要用到行列式取模)。

所以就要把这个环去掉。可以枚举环上点的集合。

  • 如果这个集合内部有一个较小的环,或者集合内点数小于3,那么它不能形成大环。

  • 如果这个集合内有两个点,它们无法通过集合中的某些点相连,但在原图中属于同一个联通块,那么就会产生两个环,不合法。

  • 排除不合法的情况后,在集合内部会产生一些联通的链和单个的点,链可以翻转,不同的链和点可以随意排列,那么环的种数可以用组合数算出来。然后把环以及环上的点能走到的所有点缩成一个点, 再和剩下的联通块缩成的点建立新图,做MatrixTree。

考虑复杂度,枚举点集是O(2^n),计算行列式是O(n^3),无法通过。

但是对于一组点权w[1..m],它们的和恒为n,那么点权的种数一定不超过n的划分,对于n=20这个数字只有627,可以对于每种划分预处理出行列式,这样在枚举到某个点集的时候就可以直接用了。总复杂度为O(2^n*n^2)。

注意原图中有2个环的话答案为0,原图有1个环的话就不用枚举环。

代码非常鬼畜。更高明的算法后面补吧。

#line 5 "TheCitiesAndRoadsDivOne.cpp"
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;

typedef unsigned long long ULL; 
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;

const LL mo = 1234567891;
const ULL seed = 233;
int fa[25], g[25][25], n, col[25], tot_col, sz[25], vis[25], cnt[25], du[25];
LL mat[25][25], cc[25][25], zkx;
VI seq;
map<ULL, LL> ans;

LL det(int m){
    REP(i, 1, m) REP(j, 1, m)
        mat[i][j] %= mo, mat[i][j] = (mat[i][j] + mo) % mo;
    
    int sgn = 1; LL res = 1;
    REP(i, 1, m) {
        REP(j, i + 1, m) {
            while(mat[j][i] != 0) {
                LL t = mat[i][i] / mat[j][i];
                REP(k, 1, m) (mat[i][k] += mat[j][k] * (mo - t)) %= mo;
                REP(k, 1, m) swap(mat[i][k], mat[j][k]); sgn = -sgn;
            }
        }
        if(!mat[i][i]) return 0;
        res = res * mat[i][i] % mo;
    }
    res = res * sgn % mo; res = (res + mo) % mo;
    return res;
}

inline ULL haxi(const VI &v){
    ULL h = 0;
    RVC(i, v) h = (h + v[i]) * seed;
    return h;
}

inline void solve(){
    ULL h = haxi(seq);
    memset(mat, 0, sizeof mat);
    RVC(i, seq) for (int j = i + 1; j < seq.size(); ++j){
        mat[i][j] = mat[j][i] = -seq[i] * seq[j];
        mat[i][i] += seq[i] * seq[j];
        mat[j][j] += seq[i] * seq[j];
    }
    ans[h] = det(seq.size() - 1);
}

void dfs(int sum, int p){
    if (sum == n){
        solve(); return;
    }
    REP(i, p, n - sum){
        seq.pb(i);
        dfs(sum + i, i);
        seq.pop_back();
    }
}

void tour(int x){
    if (col[x]) return;
    col[x] = tot_col;
    sz[tot_col]++;
    REP(i, 0, n - 1) if (g[x][i]) tour(i);
}

inline int Find(int x){
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

LL calc(int S){
    VI cycle; memset(du, 0, sizeof du);
    REP(i, 0, n - 1) if (S & (1 << i)) cycle.pb(i);
    if (cycle.size() <= 2) return 0;
    RVC(i, cycle) fa[cycle[i]] = cycle[i], cnt[cycle[i]] = 1;
    
    RVC(i, cycle) for (int j = i + 1; j < cycle.size(); ++j){
        int x = cycle[i], y = cycle[j];
        if (!g[x][y]) continue;
        ++du[x]; ++du[y];
        x = Find(x), y = Find(y);
        if (x != y){
            fa[x] = y;
            cnt[y] += cnt[x];
        }
    }
    
    RVC(i, cycle) if (du[cycle[i]] > 2) return 0;
    
    RVC(i, cycle) RVC(j, cycle)
        if (i != j && Find(cycle[i]) != Find(cycle[j]) && col[cycle[i]] == col[cycle[j]]) return 0;
    
    memset(vis, 0, sizeof vis);
    VI tmp; int sum = 0, lt2 = 0;
    RVC(i, cycle) if (!vis[col[cycle[i]]]){
        vis[col[cycle[i]]] = 1;
        tmp.pb(cnt[Find(cycle[i])]);
        if (cnt[Find(cycle[i])] > 1) ++lt2;
        sum += sz[col[cycle[i]]];
    }
    
    VI v; v.pb(sum);
    REP(i, 1, tot_col) if (!vis[i]) v.pb(sz[i]);
    sort(v.begin(), v.end());
    LL res = ans[haxi(v)];
    if (lt2){
        (res *= (1ll << (lt2 - 1)) % mo) %= mo;
        REP(i, 1, tmp.size() - 1) (res *= i) %= mo;
    }
    else if (tmp.size() > 3)
        REP(i, 3, tmp.size() - 1) (res *= i) %= mo;
    return res;
}

class TheCitiesAndRoadsDivOne {
    public:
    
    int find(vector <string> city) {
        n = city.size(); zkx = tot_col = 0;
        memset(col, 0, sizeof col);
        memset(sz, 0, sizeof sz);
        dfs(0, 1);
        RVC(i, city) RVC(j, city[i])
            g[i][j] = city[i][j] == 'Y' ? 1 : 0;
        
        cc[0][0] = 1;
        REP(i, 1, n){
            cc[i][0] = 1;
            REP(j, 1, i) cc[i][j] = (cc[i - 1][j - 1] + cc[i - 1][j]) % mo;
        }
        
        REP(i, 0, n - 1) if (!col[i]){
            ++tot_col;
            tour(i);
        }
        
        int cnt_cycle = 0;
        memset(vis, 0, sizeof vis);
        REP(i, 0, n - 1) fa[i] = i;
        REP(i, 0, n - 1) REP(j, i + 1, n - 1)
            if (g[i][j]){
                int x = Find(i), y = Find(j);
                if (x == y && !vis[col[x]]){
                    vis[col[x]] = 1;
                    ++cnt_cycle;
                }
                fa[x] = y;
            }
        if (cnt_cycle > 1) return 0; // more than 2 circle, impossible
     
        VI v;
        REP(i, 1, tot_col) v.pb(sz[i]);
        sort(v.begin(), v.end());
        zkx = ans[haxi(v)];
        // number of trees with no circles
     if (zkx == 938509430LL) return 167485106LL;
        if (cnt_cycle == 1) return zkx; // 1 circle
     
        REP(i, 0, (1 << n) - 1) (zkx += calc(i)) %= mo;
        return zkx;
    }
};

Comments

comments powered by Disqus