Luogu P3577 [POI2014]TUR-Tourism

浅浅的花香味﹌ 2021-12-20 10:23 192阅读 0赞

# Luogu P3577 \[POI2014\]TUR-Tourism #

[题目链接][Link 1]

题目大意：给出一张\\(n\\)个点，\\(m\\)条边的无向图，保证任意两点之间没有点数超过\\(10\\)的简单路径。选择第\\(i\\)个点要支付\\(C\_i\\)的代价，要求用最小的代价使得每个点被选择或者与一个被选择的点相邻。

\\(n\\leq 20000,m\\leq 25000,C\_i\\leq 1000\\)。

可以发现，如果原问题是在树上的话就很简单。所以我们先建出\\(dfs\\)树。因为这是无向图，所以所有的非树边都是返祖边。由题目中那个神奇的性质，我们可以知道，这棵树的深度不超过\\(10\\)。

于是我们可以状压。设\\(f\_\{i,S\}\\)表示第\\(i\\)个点，其祖先的状态为\\(S\\)的最小代价。

状压的状态有三种：

0：没有选择且没被覆盖

1.没有选择但被覆盖了

2.选择了

转移就有点厉害，据说是**泛化背包**。

当由\\(fa\_v\\)递归到\\(v\\)的时候，\\(dfs\\)序比\\(v\\)小的点中除了\\(v\\)到根这条链上都已经被覆盖了。然后将\\(f\_\{fa\_v,S\}\\)的\\(DP\\)值继承给\\(f\_\{v,S'\}\\)。继承的时候讨论是否选择\\(v\\)得到\\(S'\\)。

一直递归到底后回溯，\\(f\_\{fa\_v,S\}=\\min\\\{f\_\{v,S+3^\{dep\_v\}\},f\_\{v,S+2\*3^\{dep\_v\}\}\\\}\\)。接着递归下一个儿子。这个\\(DP\\)是按\\(dfs\\)序来的，当一个点出栈了过后，保证这个点已经被覆盖，无需再考虑。

\\(DP\\)的结果就是\\(\\min\\\{f\_\{root,1\},f\_\{root,2\}\\\}\\)。将每个联通块的答案加起来就行了。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 20005
    #define M 25005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    int n,m,C[N];
    struct road {int to,nxt;}s[M<<1];
    int h[N],cnt;
    void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
    int pw[15];
    bool vis[N];
    int fa[N],dep[N];
    
    int f[12][60000];
    void dfs(int v) {
        vis[v]=1;
        if(dep[v]==0) {
            f[0][0]=0;
            f[0][1]=1e9;
            f[0][2]=C[v];
        } else {
            for(int i=h[v];i;i=s[i].nxt) {
                int to=s[i].to;
                if(vis[to]) fa[v]|=1<<dep[to];
            }
            for(int S=0;S<pw[dep[v]+1];S++) f[dep[v]][S]=1e9;
            for(int S=0;S<pw[dep[v]];S++) {
                if(f[dep[v]-1][S]>=1e9) continue ;
                bool flag=0;
                for(int i=0;i<dep[v];i++) if((fa[v]>>i&1)&&S/pw[i]%3==2) flag=1;
                f[dep[v]][S+flag*pw[dep[v]]]=min(f[dep[v]][S+flag*pw[dep[v]]],f[dep[v]-1][S]);
                int T=S+2*pw[dep[v]];
                for(int i=0;i<dep[v];i++) if((fa[v]>>i&1)&&S/pw[i]%3==0) T+=pw[i];
                f[dep[v]][T]=min(f[dep[v]][T],f[dep[v]-1][S]+C[v]);
            }
        }
        int flag=0;
        for(int i=h[v];i;i=s[i].nxt) {
            int to=s[i].to;
            if(vis[to]) continue ;
            dep[to]=dep[v]+1;
            dfs(to);
            for(int S=0;S<pw[dep[v]+1];S++) {
                f[dep[v]][S]=min(f[dep[to]][S+pw[dep[to]]],f[dep[to]][S+2*pw[dep[to]]]);
            }
        }
    }
    
    int main() {
        pw[0]=1;
        for(int i=1;i<=10;i++) pw[i]=pw[i-1]*3;
        n=Get(),m=Get();
        for(int i=1;i<=n;i++) C[i]=Get();
        for(int i=1;i<=m;i++) {
            int a=Get(),b=Get();
            add(a,b),add(b,a);
        }
        int ans=0;
        for(int i=1;i<=n;i++) {
            if(vis[i]) continue ;
            dfs(i);
            ans+=min(f[0][1],f[0][2]);
        }
        cout<<ans;
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10977867.html

[Link 1]: https://www.luogu.org/problemnew/show/P3577