Bonds

题意：

求无向图所有最小割中每条边的出现次数。

题解：

每个最小割将图分为两个连通块。每个连通块（连通的顶点子集生成子图），若其剩余图（顶点补集的生成子图）也是一个连通块，则两个连通块间的边组成一个最小割，所以枚举所有的连通块能统计出所求次数。需要完成两项任务：
(1)任意一个顶点子集是否生成连通块？
(2)已知最小割，如何统计连接两个连通块间的边？
第1项任务用并查集判断每个子集的连通性，计算复杂性是 ，会超时。状压DP可以提高效率至 ，用二进制位串表示顶点子集。若顶点i不在顶点子集S，且与S中某个点有边，则S{i}也是连通块。据此进行状态转移。
第2项任务如果枚举最小割的每条边，计算复杂性也会高达 。逆向思维一下，一条边不在最小割的次数如果知道，最小割的总数减去这个次数就是答案。那么边(u,v)不在最小割有多少次？这个问题等价于在最小割形成的连通块集合中统计(u,v)的超集个数，高维前缀和的SoSDP能 时间内解决。具体用dp[s][b]表示限第0~b点可变的s的超集个数，对所有能由最小割形成的连通块，置初值dp[s][-1]=1。然后使用状态转移方程：

滚动数组优化一下空间。代码如下：

    for (int b = 0; b < n; b++)
        for (int s = (1<<n) - 1; s >= 0; s--)
            if (!(s & (1<<b)))
                dp[s] += dp[s | (1<<b)];

完整代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;
int adj[20]; // 位串形式的邻接矩阵
int u[1 << 20], v[1 << 20];
bool c[1 << 20]; // c[s]=1: 点集s是连通的
int dp[1 << 20]; // 点集被包含的连通分支数

void ConnectBlock()//求图中所有的联通块
{
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; i++)
        c[1 << i] = 1;
    for (int s = 0; s < (1 << n); s++)
        if (c[s])
            for (int i = 0; i < n; i++)
                if ((s & (1 << i)) == 0 && (adj[i] & s))
                    c[s | (1 << i)] = 1; // 顶点i不在s，且与s中某个点有边
}

int main()
{
    int t, x, y;
    scanf("%d", &t);
    for (int cs = 1; cs <= t; cs++)
    {
        scanf("%d%d", &n, &m);
        memset(adj, 0, sizeof(adj));
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            adj[x] |= (1 << y);
            adj[y] |= (1 << x);
            u[i] = x;
            v[i] = y;
        }
        ConnectBlock();
        int tot = 0;
        for (int s = 0; s < (1 << n); s++)
        {
            int r = (~s) & ((1 << n) - 1);//补集
            if (s > r)
                break;
            if (c[s] && c[r])
            {
                dp[s] = dp[r] = 1;
                tot++;
            }
        }
        //SoSDP求超集
        for (int b = 0; b < n; b++)
            for (int s = 0; s < (1 << n); s++)
                if (!(s & (1 << b)))
                    dp[s] += dp[s | (1 << b)];
        printf("Case #%d:", cs);
        for (int i = 0; i < m; i++)
            printf(" %d", tot - dp[(1 << u[i]) | (1 << v[i])]);
        printf("\n");
    }
    return 0;
}