2014寒假总结(1.18-1.20)

Jan 18th

生成树计数:Kirchhoff矩阵的构造

long long Kirchhoff()
{
    long long ret=1;
    for (int i=1; i<N; i++)
    {
        for (int j=i+1; j<N; j++)
            while (C[j][i]) // 初等行变化不改变行列式的值,可用Euclid取模
         {
                long long t=C[i][i]/C[j][i];
                for (int k=i; k<N; k++) C[i][k]-=t*C[j][k];
                for (int k=i; k<N; k++) std::swap(C[i][k], C[j][k]);
                ret*=-1;
            }
    }
    for (int i=1; i<N; i++) ret=ret*C[i][i];
    return ret;
}

Jan 19th

【NOI2007】生成树计数 最小表示法+矩阵快速幂

可以通过DFS预处理出初始状态与转移矩阵,然后就上快速幂乱搞即可。

【AHOI2006】上学路线 最短路+最小割

对原图求一次SPFA,记D[u]为S到u的最短距离,将所有满足D[u]+W(u,v)==D[v]的边加入新图中,容易知道新图的任意一条路径都是原图的最短路,新图的最小割即为题目最优解。

【SCOI2011】地板 独立插头DP。

插头表示3个状态:无插头,插头已经转弯,插头未转弯。

【HNOI2007】神奇游乐园 插头DP单回路

其实就是简单的单回路DP,只是不同于Formula 1,不是哈密尔顿回路。在空格时转移时可以不新增插头。

【JSOI2008】星球大战 离线+并查集

离线倒过来处理就变成在连通块之间加边的经典问题了。

Jan 20th

【CQOI2006】移动棋子 枚举+KM/费用流+BFS

分析发现棋子之间移动的顺序并不影响答案,所以只需要枚举可行的目标状态,每次跑一遍费用流,取最小值即可。