zkx06111's Blog

SRM 705 450pts MovingTokens

| Comments

题意

一开始n个点每个节点上都有小球。给出一些表示小球方向的有向图,一个图中每个节点有且仅有一条出边,表示使用这个有向图之后某个节点上的小球移动到另一个节点上。求经过无限次移动(顺序可以自行决定)之后,有小球的节点数最少是多少。

题解

可以处理出所有能通过一些操作走到一起的点对(i, j),并保存方案。如果当前没有两个非空盒子满足可以走到一起,那么就停止操作,输出非空盒子的个数;否则就执行让它们走到一起的方案。

证明:设在开始合并点对(i, j)之前执行过的操作序列为S,那么只需要在合并完(i, j)之后再次执行S,执行完之后非空盒子的集合一定是合并(i, j)前非空盒子集合的子集,这说明把合并(i, j)对最终答案没有影响。

杜教的代码使用了从终点出发倒着dfs优雅地算出了可以合并的点对以及方案,于是感觉自己写的代码就是一坨翔。

int in[55], equ[55][55], g[55][55], nxt[55][55], tmp[55];
vector<VI> fr[55][55];

class MovingTokens {
    public:
    
    void dfs(int x, int y){
        equ[x][y] = 1;
        RVC(i, fr[x][y]){
            VI p = fr[x][y][i];
            int u = p[0], v = p[1];
            if (!equ[u][v]){
                nxt[u][v] = p[2];
                dfs(u, v);
            }
        }
    }

    int move(int n, int m, vector <int> moves) {
        memset(equ, 0, sizeof equ);
        REP(i, 0, n - 1) REP(j, 0, n - 1) fr[i][j].clear();
        REP(i, 0, n - 1) in[i] = 1;
        REP(i, 0, n - 1) REP(j, 0, m - 1)
            g[j][i] = moves[j * n + i];
        REP(i, 0, m - 1) REP(j, 0, n - 1) REP(k, 0, n - 1){
            VI v; v.pb(j); v.pb(k); v.pb(i);
            fr[g[i][j]][g[i][k]].pb(v);
        }
        REP(i, 0, n - 1) if (!equ[i][i]) dfs(i, i);
        while (1){
            int fl = 0;
            REP(i, 0, n - 1) REP(j, i + 1, n - 1) if (equ[i][j] && in[i] && in[j]){
                fl = 1;
                int x = i, y = j;
                while (x != y){
                    int w = nxt[x][y];
                    x = g[w][x]; y = g[w][y];
                    debug("%d %d\n", x, y);
                    REP(p, 0, n - 1) tmp[p] = in[p], in[p] = 0;
                    REP(p, 0, n - 1) in[g[w][p]] |= tmp[p];
                }
            }
            if (!fl) break;
        }
        int ans = 0;
        REP(i, 0, n - 1) ans += in[i];
        return ans;
    }

};

Comments

comments powered by Disqus