2019 Multi-University Training Contest 8 1008 Andy and Maze 状压DP + color coding
DP   发布于 2019-08-15   518人围观  0条评论
DP   发表于 2019-08-15   518人围观  0条评论

题目大意

求以任意点为起点的长度为k的路径的距离的最大值,如果没有这样的路径输出impossible。

题解

Nanjing University的同学们在写题解的时候真的是高估了我的英文水平……看了两个小时才看懂这个题……

那么这篇就相当于把Nanjing University的同学们的英文题解翻译一遍搬过来。

首先,这种题目是一种典型的模型。

这种题有两种做法,一种是分别固定起点,然后不断地跑bfs。不过这种方法可能不适合这种数据范围。

那么介绍第二种做法,color coding。

简单来说,就是对每个点进行随机染色,之后用状压DP的思想,求出dp[v][sum],表示以v为中止点,sum为当前走过的颜色的的二进制位表示(注意不能走同颜色的点)时的距离的最大值。

于是我们就是需要统计dp[1...n][(1<<k)-1]中的最大值作为我们的答案。这样做时间复杂度是O(2km)的

不过很明显这样的做法是并不一定能够正确的,因为很有可能我们把本应成为答案的部分中的点随机成为颜色相同的点,从而不能够同时去走。

所以说color coding实际上是一种具有成功概率性的思路。最优路径上的点的颜色全部是不同的概率为k!/kk,所以我们期望做kk/k!次这样的过程,就有较大概率能够算出最优答案。

通过多次测试,color coding这样的思路就可以不断逼近正确答案。

最终此题的复杂度就是做一次的复杂度乘做的次数。

By the way,我在hdu上交的时候运行300次就T了,而运行200次可以AC,题解代码给的是250次。。。看起来这个还是有点看脸的?

代码

#include <bits/stdc++.h>
using namespace std;
int t,n,m,k;
const int maxn = 2e4+5;
struct edge{
    int to,next,dis;
}e[maxn<<1];
int h[maxn];
int dp[maxn][70];
int cnt = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].dis = d;e[cnt].next = h[u];
    h[u] = cnt++;
    return;
}
int u,v,w;
int color[maxn];
int work(){
    int ans = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 0;j < (1 << k);++j){
            dp[i][j] = -1;
        }
    }
    for(int i = 1;i <= n;++i){
        color[i] = rand() % k;
        dp[i][(1<<color[i])] = 0;
    }
    for(int p = 0;p < (1<<k);++p){
        for(int i = 1;i <= n;++i){
            if(p & (1 << color[i])){
                for(int j = h[i];j != -1;j = e[j].next){
                    int u = e[j].to;
                    if(dp[u][p ^ (1 << color[i])] >= 0){
                        dp[i][p] = max(dp[i][p],dp[u][p^(1 << color[i])] + e[j].dis);
                    }
                }
            }
        }
    }
    for(int i = 1;i <= n;++i){
        ans = max(ans,dp[i][(1<<k)-1]);
    }
    return ans;
}
int main(){
    srand(time(NULL));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        for(int i = 1;i <= n;++i)
            h[i] = -1;
        cnt = 0;
        int ans = 0;
        for(int i = 1;i <= m;++i){
            cin >> u >> v >> w;
            add(u,v,w);
            add(v,u,w);
        }
        for(int i = 1;i <= 200;++i){
            ans = max(ans,work());    
        }
        if(ans == 0)cout << "impossible\n";
        else cout << ans << "\n";
    }
    return 0;
}

 

上一篇: CCPC 2017-2018 Finals HDU 6252 Subway Chasing 差分约束系统

下一篇: 2019 Multi-University Training Contest 7 1010 Just Repeat

立即登录,发表评论
没有帐号?立即注册
0 条评论