洛谷P3577 [POI2014]TUR-Tourism

题目描述

King Byteasar believes that Byteotia, a land full of beautiful sights, should attract lots of tourists, who should spend lots of money, which should eventually find their way to the royal treasury.

But reality does not live up to his dream.

So the king instructed his councilor to look into this issue.

The councilor found out that foreigners keep away from Byteotia due to its sparse road network.

Let us remark that there are $n$ towns in Byteotia, connected by $m$ two way roads, each road linking two different towns.

The roads may lead through picturesque overflies and somewhat less picturesque tunnels.

There is no guarantee that every town can be reached from every other town.

The councilor observed that the current road network does not allow for a long journey.

Namely, wherever one starts the journey, it is impossible to visit more than 10 towns without passing through some town twice.

Due to limited funds in the treasury, no new roads will be constructed at the time.

Instead, Byteasar has decided to build a network of tourist information points (TIPs), staffed by officers who are to advertise the short trips that are available.

For each town, there should be a TIP either in this town or one of the towns directly linked by a road.

Moreover, the cost of building the TIP is known for each town.

Help the king by finding the cheapest way of building TIPs that will satisfy aforementioned condition.

给定一个n个点，m条边的无向图，其中你在第i个点建立旅游站点的费用为Ci。在这张图中，任意两点间不存在节点数超过10的简单路径。请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。

输入输出格式

输入格式：

The first line of the standard input contains two integers $n$ , $m$ ( $2\le n\le 20\ 000$ , $0\le m\le 25\ 000$ ), separated by a single space, that specify the number of towns and roads in Byteotia respectively.

The towns are numbered from $1$ to $n$ .

The second line of input contains $n$ integers $c_1,c_2,\cdots,c_n$ ( $0\le c_i\le 10\ 000$ ), separated by single spaces; the number $c_i$ specifies the cost of building a TIP in the town no. $i$ .

Then, a description of the Byteotian road network follows. The $i$ -th of the following $m$ lines contains two integers $a_i$ , $b_i$ ( $1\le a_i<b_i\le n$ ), separated by a single space, that indicate that the towns no. $a_i$ and $b_i$ are linked by a road. There is at most one (direct) road between any pair of towns.

输出格式：

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

输入输出样例

输入样例#1：复制

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

输出样例#1：复制

说明

看到最长路径不超过10就应该是状态压缩了。

问题是如何压，如何转？

考虑任意两点之间的距离不超过10，那么dfs树的深度也不会超过10，我们可以记忆化搜索。状态压缩到根路径上的点。

此时，我们对于一个点，只考虑它向层数比他小的点连边转移。为什么一定可以转移呢？注意到DFS树的一个性质：一个点除树边外的边一定连向祖先(我太菜了没发现这一点)。

那么就好说了，我们记dp[i][mask]表示i节点从自己到根节点路径上状态为mask的最小代价。转移就有两种：1、当前节点选，从父亲转移下来，令连边祖先中所有的未满足的点都变为满足。(这就需要0,1,2三种状态，表示没选满足，选了，没选未满足) 2、当前节点未选，那么根据祖先获取当前点的状态。这样我们可以直接推出到达叶子节点时每种状态的最小代价。我们再记g[i][mask]表示i的子树都满足条件且祖先状态为mask的最小代价，这样我们可以根据dp数组再上推出根的答案。因为只根据dp数组的叶子节点上推，我们可以把g数组和dp数组用一个数组存。

#pragma GCC optimize("O2")
#include<cstdio>
#include<iostream>
#include<cstring>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2.5e4 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, next;
}e[maxn << 1];
int head[maxn], cnt;
inline void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0;static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
int pow[15];
void init() {
    pow[0] = 1;
    For(i, 1, 12) pow[i] = pow[i - 1] * 3;
}

int dp[11][60005], vis[maxn], anc[maxn], w[maxn], d[maxn];

void DP(int u) {
    vis[u] = 1;
    int isc = 1, st, v, step = d[u], p, np;
    p = pow[step], np = p * 3;
    if(step == 0) dp[0][0] = w[u], dp[0][1] = 0, dp[0][2] = inf;
    else {
        *anc = 0;
        for(register int i = head[u]; i; i = e[i].next) {
            v = e[i].v;
            if(!vis[v]) continue;
            if(d[v] >= d[u]) continue;
            anc[++(*anc)] = pow[d[v]];
        }
        memset(dp[step], 0x3f, sizeof(int) * np);
        For(k, 0, p - 1) {
            isc = p, st = k;
            For(i, 1, anc[0]) {
                v = anc[i];
                if(k / v % 3 == 0) isc = 2 * p; 
                else if(k / v % 3 == 1) st += v;
            }
            dp[step][k + isc] = 
            min(dp[step - 1][k], dp[step][k + isc]);
            dp[step][st] = min(dp[step - 1][k] + w[u], dp[step][st]);
        }
    }
    p *= 3, np = np * 2;
    for(register int i = head[u]; i; i = e[i].next) {
        v = e[i].v;
        if(vis[v]) continue;
        d[v] = step + 1, DP(v);
        For(k, 0, p - 1)
            dp[step][k] = min(dp[step + 1][k], dp[step + 1][k + np]);
    }
}

int n, m, u, v, ans;
int main() {
    init();
    read(n), read(m);
    For(i, 1, n) read(w[i]);
    For(i, 1, m) read(u), read(v), adde(u, v), adde(v, u);
    For(i, 1, n) if(!vis[i]) 
        DP(i), ans += min(dp[0][0], dp[0][2]);
    printf("%d\n", ans);
    return 0;
}

Rockdu's Blog