@description@
给定一个n个点，m条边的无向图，其中你在第i个点建立旅游站点的费用为C[i]。在这张图中，任意两点间不存在节点数超过10的简单路径。
请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。
Input
第一行包含两个正整数n,m(1<=n<=20000,0<=m<=25000)，分别表示点数和边数。
第二行包含n个整数，其中第i个数为Ci，表示在第i个点建立旅游站点的费用。
接下来m行，每行两个正整数u,v(1<=u,v<=n)，表示u与v之间连了一条边，保证没有重边
Output
输出一行一个整数，即最小的总费用。
Sample Input
6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6
Sample Output
7
Explanation
分别在1，5，6号站点建立旅游站点。
@solution@
如果在树上做，这道题就是道树 dp 入门题。
如果在一般的图上做，这道题就是道 np 问题。
但是我们有一个 “任意两点间不存在节点数超过10的简单路径” 的条件，这使我们联想到状压/搜索。
考虑将图转为树，建出每一个连通子图（注意不一定整张图连通）的 dfs 树，由上面那个条件我们有树的深度 <= 10。
考虑 dfs 树的性质：边要么是树边要么是返祖边。这意味着一个点连向它祖先的边 <= 10。我们或许可以状压它所有祖先的状态。
定义状态 dp[i][s] 表示考虑 dfs 序的前 i 个元素，第 i 个元素到根的路径上所有点的状态为 s。其中根据我们树 dp 入门题的思想，将 s 的状态设为三进制，分别表示 “0 -不选且相邻点也都不选”，“1 - 不选但已经存在相邻点选”，“2 - 选”。
考虑从 dp[i][s] 转移到 dp[i+1][s']。这个过程可以看作退栈，将栈顶的不合法元素全部弹出后再在栈中加入新的元素。
首先要保证 s 中不是 i+1 祖先的点为 1 or 2，过后将它们从状态 s 中删除。转移考虑 i+1 选不选，再考虑这个决策对返祖边的影响：如果选，返祖边的 0 状态全部改为 1 状态；如果不选，如果返祖边存在一个 2 状态则 i + 1 为 1 状态，否则为 0 状态。
时间复杂度 O(3^10*(n + m))。虽然很不科学不过应该跑得挺快的。
（但我常数大加了随机选dfs树根+二进制代替三进制+转移的一点优化才过）（但我总感觉是因为加了这些东西才跑得慢）
@accepted code@
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 40000;
const int MAXM = 50000;
const int SIZE = (1<<10);
const int INF = (1<<30);
struct Graph{
struct edge{
int to; edge *nxt;
}edges[2*MAXM + 5], *adj[MAXN + 5], *ecnt;
Graph() {ecnt = &edges[0];}
void addedge(int u, int v) {
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->nxt = adj[v], adj[v] = p;
}
}G1, G2;
vector<int>vec[MAXN + 5];
int dep[MAXN + 5], dfn[MAXN + 5], tid[MAXN + 5], dcnt = 0;
void dfs(int x, int f) {
dep[x] = dep[f] + 1, tid[x] = (++dcnt), dfn[dcnt] = x;
for(Graph::edge *p=G1.adj[x];p;p=p->nxt) {
if( p->to == f ) continue;
if( !tid[p->to] )
G2.addedge(x, p->to), dfs(p->to, x);
else {
if( tid[p->to] < tid[x] )
vec[x].push_back(p->to);
}
}
}
int C[MAXN + 5];
int dp[2][SIZE + 5][SIZE + 5];
void init(int t1, int t2) {
for(int s1=0;s1<t1;s1++) {
int s2 = s1;
do {
dp[1][s1][s2] = dp[0][s1][s2];
if( !s2 ) break;
s2 = s1 & (s2 - 1);
}while( true );
}
for(int s1=0;s1<t2;s1++) {
int s2 = s1;
do {
dp[0][s1][s2] = INF;
if( !s2 ) break;
s2 = s1 & (s2 - 1);
}while( true );
}
}
int get_ans(int x, int m) {
int lst = 0; dp[0][0][0] = 0;
for(int p=tid[x];p<=tid[x]+m-1;p++) {
int i = dfn[p];
init(1<<lst, 1<<dep[i]);
int t1 = (1<<(dep[i]-1)), t2 = ((1<<(lst-(dep[i]-1)))-1)<<(dep[i]-1), t3 = t1>>1;
for(int j=0;j<vec[i].size();j++)
t3 |= (1<<(dep[vec[i][j]]-1));
for(int s3=0;s3<=t2;s3+=t1) {
for(int s1=0;s1<t1;s1++) {
int s2 = s1;
do {
int s4 = s1|t2, s5 = s2|s3;
if( dp[1][s4][s5] != INF ) {
if( s5 & t3 ) dp[0][s1|t1][s2] = min(dp[0][s1|t1][s2], dp[1][s4][s5]);
else dp[0][s1][s2] = min(dp[0][s1][s2], dp[1][s4][s5]);
dp[0][s1|t3|t1][s2|t1] = min(dp[0][s1|t3|t1][s2|t1], dp[1][s4][s5] + C[i]);
}
if( !s2 ) break;
s2 = s1 & (s2 - 1);
}while( true );
}
}
lst = dep[i];
}
int t = (1<<lst), ret = INF;
for(int i=0;i<t;i++)
ret = min(ret, dp[0][t-1][i]);
return ret;
}
int fa[MAXN + 5], siz[MAXN + 5];
int find(int x) {return fa[x] = (fa[x] == x ? x : find(fa[x]));}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if( fx != fy )
fa[fx] = fy, siz[fy] += siz[fx];
}
vector<int>v[MAXN + 5];
int main() {
srand(20040911);
int n, m; scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &C[i]), fa[i] = i, siz[i] = 1;
for(int i=1;i<=m;i++) {
int u, v; scanf("%d%d", &u, &v);
G1.addedge(u, v), unite(u, v);
}
int ans = 0;
for(int i=1;i<=n;i++)
v[find(i)].push_back(i);
for(int i=1;i<=n;i++)
if( fa[i] == i ) {
int rt = v[i][((unsigned int)(rand() << 16 | rand())) % v[i].size()];
dfs(rt, 0), ans += get_ans(rt, siz[i]);
}
printf("%d
", ans);
}
@details@
我现在还是感觉是因为我加了些奇奇怪怪的优化才跑得非常慢。
人家跑 6000ms，可我要跑 13000ms 左右。。。一开始还 T 了几发。。。
果然有些东西还是不要乱用。