2010-1125
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== 题目大意 ==
集训队分学校的奖金的时候，由于学校只把钱发给每个队第一个人，然后又由于每个人可能加入了不同的队伍，所以当刚从学校拿到钱的时候，有的人会多拿，有的人会少拿，有些人之间有一定长度的道路联通。
定义一次传送为一个人通过一个的路径把非负的钱送给另外一个人，无论钱数额多少，此过程花费为路径的长度。
现要求最终传送的结果为每个人都拿到自己应得的数额，求最小化所有传送的花费和。
== 分析 ==
这个题目可以被理解成：
* 一个无向图，有边权（非负）和点权（整数），把这个图划分成几个连通子图，在每一个子图，点权和为 0，最小化 ```Sum{i 的边权利和，{i 是一个划分出的子图} }```
考虑划分出的一个子图，如果其中的点权和为 0，那么它的传送花费就是这个子图的最小生成树。
于是问题转换成把原图划分成几个点权和为 0 的连通子图，最小化它们的 MST 和。
== 算法 ==
用 f(bit_mask)，bit_mask 按位选取了一些点（人），来表示：
* 将这些人分成一个子图（不排除进一步划分），所需传送的最小花费。
那么最终解就是 f((1 << n) -1)。
f(x) 有意义仅当 x 选取的点权和为 0 并且这些点是连通的。
对于有意义的 f(x)，可以将 x 进一步划分为 ```x1 | x2```，其中 ```(x1 & x2) == 0```，返回 ```min{f(x1) + f(x2), MST(nodes selected by x)}``` 。枚举这个划分复杂度 ```O(popcount(x)^3)```
f(x) 满足全局最优子问题也最优，并且划分没有后效性，可以记忆化。
== 参考程序 ==
{{{
#!cpp
#include <cassert>
#include <cstdio>
#include <iostream>
#include <bitset>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
namespace debug {
static const bool DEBUG = false;
#define D if(debug::DEBUG)
static int _callstack_depth;
template <class R>
class _scoped_callstack_info {
const R* pr;
void indent() {
D for (int i = 0; i < _callstack_depth * 2; i++) cout << ' ';
}
public:
_scoped_callstack_info(const R& r = NULL) {
D {
indent();
pr = &r;
_callstack_depth++;
}
}
~_scoped_callstack_info() {
D {
_callstack_depth--;
if (pr) indent(), cout << "res = " << *pr << endl;
}
}
};
#define CALLSTACK_INFO(v, r) \
debug::_scoped_callstack_info<__typeof(r)> _callstack_info(r);\
D std::cout << __func__ << "(" << v << ")" << std::endl;
}
const int N = 16;
const int M = 128;
int n, m;
int v[N];
int fc[1 << N];
map<int, int> l2p;
#ifndef ONLINE_JUDGE
__attribute__((__constructor__))
#endif
void l2p_init() {
int v = 1;
for (int i = 0; i < N; i++) {
l2p[v] = i;
v <<= 1;
}
}
template<int n>
struct DisjointSet {
int p[n];
DisjointSet() {
for (int i = 0; i < n; i++) p[i] = i;
}
inline int find(int x) {
if (p[x] == x) return x; else return p[x] = find(p[x]);
}
inline void join(int x, int y) {
p[find(x)] = find(y);
}
inline bool isjoint(int x, int y) {
return find(x) == find(y);
}
};
struct Edge;
Edge* em[N][N];
struct Edge {
int p[2];
int w;
void read() {
scanf("%d%d%d", &p[0], &p[1], &w);
// fill in matrix
em[p[0]][p[1]] = em[p[1]][p[0]] = this;
}
bool operator < (const Edge& rhs) const {
return w < rhs.w;
}
} e[M], etmp[M];
int etmpc;
int ids[N], idsc = 0;
int f(int mask) {
if (fc[mask] == -1) {
int r = -2;
// CALLSTACK_INFO("mask: " << mask, r);
{
// judge if these points sum up equals zero
int sum = idsc = 0;
int t = mask;
while (t != 0) {
sum += v[ids[idsc] = l2p.find(t & (-t))->second];
// D printf("ids[%d] = %d\n", idsc, ids[idsc]);
t = t & (t - 1);
idsc ++;
}
D printf(" sum = %d\n", sum);
// sum != zero, invalid cut
if (sum != 0) { r = -3; goto ret; }
// judge connectivity (M) (combined in calculating MST)
// if (!connected(mask, mask & (-t))) return -3;
// collect edges and do mst ... O(? mask * N^2)
etmpc = 0;
for (int i = 0; i < idsc; i++) {
for (int j = i + 1; j < idsc; j++) {
// D printf(" i, j = %d, %d | %p\n", i, j, em[ids[i]][ids[j]]);
if (em[ids[i]][ids[j]] != NULL) {
etmp[etmpc++] = *em[ids[i]][ids[j]];
}
}
}
sort(etmp, etmp + etmpc);
int joint_w = 0, joint_n = 0;
{
DisjointSet<N> d;
for (int i = 0; i < etmpc; i++) {
// try add edge etmp[i]
Edge& edge = etmp[i];
if (!d.isjoint(edge.p[0], edge.p[1])) {
// add that edge
d.join(edge.p[0], edge.p[1]);
joint_n++;
joint_w += edge.w;
// D printf("add edge.w = %d\n", edge.w);
if (joint_n == idsc - 1) {
// ok
break;
}
}
}
}
// D printf("j_n = %d, j_w = %d\n", joint_n, joint_w);
if (joint_n == idsc - 1) r = joint_w; else r = -4;
// cut to 2 pieces, and get result
for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
int incsub = ~sub & mask;
// if (sub > incsub) break;
int r1 = f(sub), r2;
if (r1 >= 0) {
r2 = f(incsub);
if (r2 >= 0) {
r1 += r2;
if (r < 0 || r1 < r) r = r1;
}
}
}
}
ret:
fc[mask] = r;
}
return fc[mask];
}
int main(int argc, char const* argv[]) {
#ifdef ONLINE_JUDGE
l2p_init();
#endif
while (scanf("%d%d", &n, &m) == 2) {
D puts("========================");
assert(n >= 2 and n <= N);
assert(m >= 0 and m <= n * (n - 1) / 2);
memset(fc, -1, sizeof(fc));
memset(em, 0, sizeof(em));
for (int i = 0; i < n; i++) scanf("%d", &v[i]);
for (int i = 0; i < m; i++) e[i].read();
int r = f((1 << n) - 1);
if (r < 0) puts("Impossible");
else printf("%d\n", r);
}
return 0;
}
}}}题目大意
集训队分学校的奖金的时候，由于学校只把钱发给每个队第一个人，然后又由于每个人可能加入了不同的队伍，所以当刚从学校拿到钱的时候，有的人会多拿，有的人会少拿，有些人之间有一定长度的道路联通。
定义一次传送为一个人通过一个的路径把非负的钱送给另外一个人，无论钱数额多少，此过程花费为路径的长度。
现要求最终传送的结果为每个人都拿到自己应得的数额，求最小化所有传送的花费和。
分析
这个题目可以被理解成：
- 一个无向图，有边权（非负）和点权（整数），把这个图划分成几个连通子图，在每一个子图，点权和为 0，最小化 ``
Sum{i 的边权利和，{i 是一个划分出的子图} }``
考虑划分出的一个子图，如果其中的点权和为 0，那么它的传送花费就是这个子图的最小生成树。
于是问题转换成把原图划分成几个点权和为 0 的连通子图，最小化它们的 MST 和。
算法
用 f(bit_mask)，bit_mask 按位选取了一些点（人），来表示：
- 将这些人分成一个子图（不排除进一步划分），所需传送的最小花费。
那么最终解就是 f((1 << n) -1)。
f(x) 有意义仅当 x 选取的点权和为 0 并且这些点是连通的。
对于有意义的 f(x)，可以将 x 进一步划分为 ``x1 | x2`，其中 `(x1 & x2) == 0`，返回 `min{f(x1) + f(x2), MST(nodes selected by x)}` 。枚举这个划分复杂度 `O(popcount(x)^3)``
f(x) 满足全局最优子问题也最优，并且划分没有后效性，可以记忆化。
参考程序
#include <cassert>
#include <cstdio>
#include <iostream>
#include <bitset>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
namespace debug {
static const bool DEBUG = false;
#define D if(debug::DEBUG)
static int _callstack_depth;
template <class R>
class _scoped_callstack_info {
const R* pr;
void indent() {
D for (int i = 0; i < _callstack_depth * 2; i++) cout << ' ';
}
public:
_scoped_callstack_info(const R& r = NULL) {
D {
indent();
pr = &r;
_callstack_depth++;
}
}
~_scoped_callstack_info() {
D {
_callstack_depth--;
if (pr) indent(), cout << "res = " << *pr << endl;
}
}
};
#define CALLSTACK_INFO(v, r) \
debug::_scoped_callstack_info<__typeof(r)> _callstack_info(r);\
D std::cout << __func__ << "(" << v << ")" << std::endl;
}
const int N = 16;
const int M = 128;
int n, m;
int v[N];
int fc[1 << N];
map<int, int> l2p;
#ifndef ONLINE_JUDGE
__attribute__((__constructor__))
#endif
void l2p_init() {
int v = 1;
for (int i = 0; i < N; i++) {
l2p[v] = i;
v <<= 1;
}
}
template<int n>
struct DisjointSet {
int p[n];
DisjointSet() {
for (int i = 0; i < n; i++) p[i] = i;
}
inline int find(int x) {
if (p[x] == x) return x; else return p[x] = find(p[x]);
}
inline void join(int x, int y) {
p[find(x)] = find(y);
}
inline bool isjoint(int x, int y) {
return find(x) == find(y);
}
};
struct Edge;
Edge* em[N][N];
struct Edge {
int p[2];
int w;
void read() {
scanf("%d%d%d", &p[0], &p[1], &w);
// fill in matrix
em[p[0]][p[1]] = em[p[1]][p[0]] = this;
}
bool operator < (const Edge& rhs) const {
return w < rhs.w;
}
} e[M], etmp[M];
int etmpc;
int ids[N], idsc = 0;
int f(int mask) {
if (fc[mask] == -1) {
int r = -2;
// CALLSTACK_INFO("mask: " << mask, r);
{
// judge if these points sum up equals zero
int sum = idsc = 0;
int t = mask;
while (t != 0) {
sum += v[ids[idsc] = l2p.find(t & (-t))->second];
// D printf("ids[%d] = %d\n", idsc, ids[idsc]);
t = t & (t - 1);
idsc ++;
}
D printf(" sum = %d\n", sum);
// sum != zero, invalid cut
if (sum != 0) { r = -3; goto ret; }
// judge connectivity (M) (combined in calculating MST)
// if (!connected(mask, mask & (-t))) return -3;
// collect edges and do mst ... O(? mask * N^2)
etmpc = 0;
for (int i = 0; i < idsc; i++) {
for (int j = i + 1; j < idsc; j++) {
// D printf(" i, j = %d, %d | %p\n", i, j, em[ids[i]][ids[j]]);
if (em[ids[i]][ids[j]] != NULL) {
etmp[etmpc++] = *em[ids[i]][ids[j]];
}
}
}
sort(etmp, etmp + etmpc);
int joint_w = 0, joint_n = 0;
{
DisjointSet<N> d;
for (int i = 0; i < etmpc; i++) {
// try add edge etmp[i]
Edge& edge = etmp[i];
if (!d.isjoint(edge.p[0], edge.p[1])) {
// add that edge
d.join(edge.p[0], edge.p[1]);
joint_n++;
joint_w += edge.w;
// D printf("add edge.w = %d\n", edge.w);
if (joint_n == idsc - 1) {
// ok
break;
}
}
}
}
// D printf("j_n = %d, j_w = %d\n", joint_n, joint_w);
if (joint_n == idsc - 1) r = joint_w; else r = -4;
// cut to 2 pieces, and get result
for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
int incsub = ~sub & mask;
// if (sub > incsub) break;
int r1 = f(sub), r2;
if (r1 >= 0) {
r2 = f(incsub);
if (r2 >= 0) {
r1 += r2;
if (r < 0 || r1 < r) r = r1;
}
}
}
}
ret:
fc[mask] = r;
}
return fc[mask];
}
int main(int argc, char const* argv[]) {
#ifdef ONLINE_JUDGE
l2p_init();
#endif
while (scanf("%d%d", &n, &m) == 2) {
D puts("========================");
assert(n >= 2 and n <= N);
assert(m >= 0 and m <= n * (n - 1) / 2);
memset(fc, -1, sizeof(fc));
memset(em, 0, sizeof(em));
for (int i = 0; i < n; i++) scanf("%d", &v[i]);
for (int i = 0; i < m; i++) e[i].read();
int r = f((1 << n) - 1);
if (r < 0) puts("Impossible");
else printf("%d\n", r);
}
return 0;
}