1007. Message_Passing

Brief description:

… 给定一个无向图，每一个人初始有一个信息，每一步，可以选择一个人将它所知的所有信息告诉给与她相邻的另一个人。
。。要使得最后每个人都获得所有人的信息，最少需要多少步，满足最少步数条件下，有多少种不同的方案。

Analysis:

容易发现信息一定是先到一个汇点，再从这个汇点分发出去。。

设 F[u] 表示以 u 为根的子树，汇聚到 u 点时的方案数。

void dfs0(int u){
    F[u] = sz[u] = 1; int cur = 0; REP_G(i, u){
        del(i^1), dfs0(v);
        sz[u] += sz[v], cur += sz[v];
        F[u] *= F[v] * C(cur, sz[v]);
    }
}

设 P[u] 表示 u 为根的子树外，汇聚到 u 点时的方案数。
。。于是可以通过另一个 dfs1() 过程，来避免枚举这个汇点。

void dfs1(int u){

    res += sqr(P[u] * F[u] * C(n-1, sz[u]-1));

    REP_G(i, u){
        P[v] = P[u] * F[u] * C(n-sz[v]-1, n-sz[u]) / (F[v] * C(sz[u]-1, sz[v]));
        //cout << v << " " << F[v] << " " << P[v] << " "<< C(n-1, sz[v]-1) << endl;
        dfs1(v);
    }
}

https://gist.github.com/lychees/6187521#file-message_passing-cpp

赛后膜拜了 wzk 巨巨的代码。。。才注意到中间的 dp 过程可以化简。。
。。。以 u 为汇点时。。方案数就是。。。 $$n!/\prod{{sz}_i}$$。。（。就是 有向树 的拓扑排序方案计数。。
。。于是就变得非常好写了。。。

https://gist.github.com/lychees/6187521#file-message_passing2-cpp

External link:

。。。

Posted by xiaodao
Category: 线上比赛