BZOJ 3836/洛谷 3577: [Poi2014]Tourism

2018-03-07Chentiancai_nn?

Description

给定一个n个点,m条边的无向图,其中你在第i个点建立旅游站点的费用为C[i]。在这张图中,任意两点间不存在节点数超过10的简单路径。

请找到一种费用最小的建立旅游站点的方案,使得每个点要么建立了旅游站点,要么与它有边直接相连的点里至少有一个点建立了旅游站点。

Input

第一行包含两个正整数n,m(1<=n<=20000,0<=m<=25000),分别表示点数和边数。

第二行包含n个整数,其中第i个数为C[i](0<=C[i]<=10000),表示在第i个点建立旅游站点的费用。

接下来m行,每行两个正整数u,v(1<=u,v<=n),表示u与v之间连了一条边,保证没有重边

Output

Your program should print out one integer to the standard output: the total cost of building all the TIPs.

输出一行一个整数,即最小的总费用。

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

HINT

分别在1,5,6号站点建立旅游站点。

题解

取一个点进行$dfs$,得到一棵$dfs$搜索树,则这棵树的深度不超过$10$,且所有额外边都是前向边。

对于每个点$x$,设$S$为三进制状态,$S$第$i$位表示根到$x$路径上深度为$i$的点的状态:

$0$:选了,$1$:没选,且没满足,$2$:没选,且已满足

设$f[i][j]$表示考虑根到$x$路径上深度为$i$的点时这些点的状态为$j$时的最小费用,然后按$DFS$序进行$DP$即可。

时间复杂度$O((N+M)\times3^{10})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Rep(i,a,b) for (int i=(b);i>=(a);--i)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}

const int N = 20005,M = 25005,MAXN = 59055,inf = 1e9;

int n,m,ans;
int head[N],nxt[M*2],to[M*2],cnt;
int f[12][MAXN],q[N],bin[15],a[N],d[N];
bool vis[N];
inline void insert(int x,int y){ to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; }
inline int get(int S,int dep){ return S/bin[dep]%3; }
void dfs(int x,int dep){
vis[x] = 1; d[x] = dep;
if(!dep) f[0][0] = a[x],f[0][1] = 0,f[0][2] = inf;
else{
int top = 0;
for(int i = head[x];i;i = nxt[i])
if(vis[to[i]] && d[to[i]] < dep) q[++top] = d[to[i]];
for(int S = 0;S <= bin[dep+1]-1;++S) f[dep][S] = inf;
for(int S = bin[dep]-1;S >= 0;--S){
int U = 1,V = S;
for(int i = 1;i <= top;++i){
if(get(S,q[i]) == 0) U = 2;
else if(get(S,q[i]) == 1)
V += bin[q[i]];
}
f[dep][S+U*bin[dep]] = min(f[dep][S+U*bin[dep]],f[dep-1][S]);
f[dep][V] = min(f[dep][V],f[dep-1][S]+a[x]);
}
}
for(int i = head[x];i;i = nxt[i])
if(!vis[to[i]]){
dfs(to[i],dep+1);
for(int S = 0;S <= bin[dep+1]-1;++S)
f[dep][S] = min(f[dep+1][S],f[dep+1][S+2*bin[dep+1]]);
}
}

int main(){
n = read(); m = read();
bin[0] = 1; for(int i = 1;i <= 10;++i) bin[i] = bin[i-1]*3;
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= m;++i){
int x = read(),y = read();
insert(x,y); insert(y,x);
}
for(int i = 1;i <= n;++i)
if(!vis[i]) dfs(i,0),ans += min(f[0][0],f[0][2]);
printf("%d\n", ans);
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close