2016-10-01

HDU 5765 Bonds【状压+高维前缀和】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5765

题意：

给定$n$个点的无向连通图，对于每一个边询问这个边在多少个极小割边集中出现。
数据范围：$ n\le 20$

分析：

首先根据极小割边集的定义，割边集恰好会将图分成两个部分，且两部分独立连通。
可以使用$bfs$的方式预处理出每个点集是否连通，具体过程就是维护两个集合，一个是已经访问过的$VISTED$，一个是所有可以访问的点$AVAIL$，每从$AVAIL$中访问一个点，就加入$VISTED$，并将与该点相连的其他点加入$AVAIL$点直到$AVAIL = VISTED$，这里很巧妙的利用了位运算。
接下来枚举每两个互补且连通的块，他们之间的边在一个极小割边集中，要将这些边加一，实现起来就是将所有边加一，两个块内部的边减一。边用点集表示，引用$q巨$的话

一条边实际上就是一个二元集，一个点集内部的边就是这个点集中的所有二元子集，于是只要对每个二元集计算它的所有超集的权值和，做一个高维前缀和即可。

高维前缀和我这个写法就是将所有当前状态子状态的答案都加到当前状态中

代码：

/*************************************************************************
    > File Name: 5765.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/1 10:24:37
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
const int maxn = 21, maxm = 5e2 + 5, maxx = 1234567;
p edge[maxn];
bool ok[maxx];
int con[maxx];
int cnt[maxx];
inline int lowbit(int a){return a & (-a);}
bool get(int NOW)
{
	int AVAIL = lowbit(NOW);
	int VISITED = 0;
	while(VISITED != AVAIL){
		int NOTYET = AVAIL ^ VISITED;
		int u = lowbit(NOTYET);
		VISITED |= u;
		AVAIL |= con[u] & NOW;
	}
	return VISITED == NOW;
}
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; ++tt){
		int n, m;scanf("%d%d", &n, &m);
		int u, v;
		memset(con, 0, sizeof(con));
		memset(ok, false, sizeof(ok));
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0; i < m; ++i){
			scanf("%d%d", &u, &v);
			edge[i] = p(u, v);
			con[1 << u] |= 1 << v;
			con[1 << v] |= 1 << u;
		}
		int tot = 0;
		int mask = (1 << n) - 1;
		for(int i = 1; i <= mask; ++i) ok[i] = get(i);
		for(int i = 1; i <= mask; ++i){
			if((i & 1) && ok[i] && ok[mask ^ i]){
				tot++;
				cnt[i]++;
				cnt[mask ^ i]++;
			}
		}
		for(int i = 0; i < n; ++i){
			for(int j = 1; j <= mask; ++j){
				if((j >> i) & 1) cnt[j] += cnt[j ^ (1 << i)];
			}
		}
		printf("Case #%d: ", tt);
		for(int i = 0; i < m; ++i){
			u = edge[i].first, v = edge[i].second;
			printf("%d%c", tot - cnt[mask ^ (1 << u) ^ (1 << v)], i == m - 1?'\n':' ');
		}
	}
	return 0;
}