题目链接

题解

显然这是个\(NP\)完全问题，此题的解决全仗任意两点间不存在节点数超过10的简单路径的性质

这意味着什么呢？

\(dfs\)树深度不超过\(10\)

\(10\)很小呐，可以状压了呢

我们发现一个点不但收祖先影响，而且受儿子影响，比较难处理

我们就先处理该点及其祖先，然后更新完儿子之后反过来用儿子更新根，就使得全局合法了

一个点显然有三种状态：

0.没被覆盖

1.被覆盖但是没有建站

2.建站

设\(f[d][s]\)表示节点\(u\)【深度为\(d\)】，其祖先【包括\(u\)】状态为\(s\)的最优解

\(dfs\)进来的时候，我们用父亲的答案更新\(u\)

\(dfs\)结束的时候，我们用儿子的答案替代\(u\)的答案，保证全局合法

复杂度\(O((n + m)3^{10})\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 20005,maxm = 50005,M = 59050,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 1;

int n,m,C[maxn],dep[maxn],vis[maxn],bin[100];

int f[11][M],st[maxn],top;  //0 not yet    1 ok but empty    2 ok and full

struct EDGE{int to,nxt;}ed[maxm];

inline void build(int u,int v){

	ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;

	ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;

}

inline int min(int a,int b){return a < b ? a : b;}

void dfs(int u){

	vis[u] = true;

	int maxv = bin[dep[u]] - 1,d = dep[u]; top = 0;

	for (int i = 0; i < bin[dep[u] + 1]; i++) f[d][i] = INF;

	Redge(u) if (vis[to = ed[k].to]) st[++top] = dep[to];

	if (!d) f[0][0] = 0,f[0][1] = INF,f[0][2] = C[u];

	for (int s = 0; s <= maxv; s++){

		int t = 0,v,p,e = s + 2 * bin[d];

		REP(i,top){

			v = st[i]; p = s / bin[v] % 3;

			if (p == 2) t = 1;

			else if (!p) e += bin[v];

		}

		f[d][s + t * bin[d]] = min(f[d][s + t * bin[d]],f[d - 1][s]);

		f[d][e] = min(f[d][e],f[d - 1][s] + C[u]);

	}

	Redge(u) if (!vis[to = ed[k].to]){

		dep[to] = dep[u] + 1;

		dfs(to);

		for (int s = 0; s < bin[d + 1]; s++)

			f[d][s] = min(f[d + 1][s + bin[d + 1]],f[d + 1][s + 2 * bin[d + 1]]);

	}

}

int main(){

	bin[0] = 1; for (int i = 1; i <= 13; i++) bin[i] = bin[i - 1] * 3;

	n = read(); m = read();

	REP(i,n) C[i] = read();

	while (m--) build(read(),read());

	int ans = 0;

	for (int i = 1; i <= n; i++)

		if (!vis[i]) dfs(i),ans += min(f[0][1],f[0][2]);

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ3836 [Poi2014]Tourism 【树形dp +状压dp】

题目链接

题解

最新文章

热门文章