NOIP2017 Day2 T2(状压DP/爆搜)

发表于 | 分类于 | | + s

Loj 2318
题意：如上。

70 分暴力：
枚举每个点作为起点并加入集合，然后从集合中找点出来拓展节点继续加入集合，然后当图连通以后就更新答案，加上可行性和最优化剪枝。时间复杂度比较高但是能过去，DFS / 搜索 / 枚举不要约束在那个板子上。
刚开始我想到是枚举整个图的生成树子集然后枚举起点计数，这样的复杂度太高了，我们调换一下搜索顺序，即先枚举起点后形成生成树子集后计数，这样免去了计数时增加的 $m$(去重以后) 的复杂度。据说爆搜剪枝剪得好能 AC Orz

100 分状压 DP :
我们发现暴力的方法很多重复的枚举，所以我们尝试在爆搜中加入 DP 思想。本题 $n$ 小并且 $m$ 可以去重，所以就可以状压 DP 了。设$dp(S)$为当前开通的点的集合的最小代价，转移就枚举每一个在$S$中的点然后再找它的邻接点并且邻接点不在$S$后 DP 转移即可。主体程序很像，但是这个方法节约很多时间。

知识点：
1、调换枚举顺序免除一些难处理的
2、时间复杂度感觉会炸不一定会炸，大胆写，但也不要 sb，剪枝写上
3、DFS 不好搜就按点枚举而不是 DFS，DFS 和搜索还是有区别
4、选择转化为添加
5、暴搜可以加入 DP 思想，所以 DP - 爆搜 - 记忆化搜索 三者有着密切关系

100分：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using std::cin; using std::cout; using std::endl;

const int MAXN = 15, INF = 1000000000;

int n, m, G[MAXN][MAXN], dp[(1 << 13) + 5], dis[MAXN], ans;

void dfs(int S) {
    //printf("S=%d\n", S);
    for (int u = 1; u <= n; ++u) if ((1 << (u - 1)) & S) {
        for (int v = 1; v <= n; ++v) if (((1 << (v - 1)) & S) == 0) {
            //printf("u=%d v=%d\n", u, v);
            if (G[u][v] == INF) continue;
            int st = 1 << (v - 1);
            if (dp[S | st] > dp[S] + G[u][v] * (dis[u] + 1)) {
                dis[v] = dis[u] + 1, dp[S | st] = dp[S] + G[u][v] * (dis[u] + 1);
                dfs(S | st);
            }
        }
    }
}

void clean() {
    ans = INF;
    for (int i = 0; i <= n; i++) 
    for (int j = 0; j <= n; j++) G[i][j] = INF;
}
int solve() {
    clean();
    for (int a, b, w, i = 1; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &w);
        G[a][b] = std::min(G[a][b], w), G[b][a] = std::min(G[b][a], w);
    }
    /*for (int i = 0; i <= n; i++) 
    for (int j = 0; j <= n; j++) printf("i=%d, j=%d, w=%d\n", i, j, G[i][j]);*/
    for (int i = 1; i <= n; i++) {
        ms(dis, 0);
        for (int j = 0; j < (1 << n); j++) dp[j] = INF;
        dp[0] = dp[1 << (i - 1)] = 0;
        dfs((1 << (i - 1)));
        ans = std::min(ans, dp[(1 << n) - 1]);
        //for (int j = 0; j < (1 << n); j++) printf("i=%d, S=%d, dp=%d\n", i, j, dp[j]);
    }
    printf("%d\n", ans);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}

70分爆搜：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 15;

int n, m, ans, G[MAXN][MAXN], vis[MAXN], dis[MAXN];

void dfs(int a, int tmp) {
    if (tmp >= ans) return ;
    if (a == n + 1) {
        ans = std::min(tmp, ans);
        //for (int i = 1; i <= n; i++) printf("%d%c", dis[i], (i == n ? '\n' : ' '));
        return ;
    }
    for (int i = 1; i <= n; i++) if (vis[i]) {
        for (int j = 1; j <= n; j++) if (i != j && G[i][j] != 1000000000 && !vis[j]) {
            vis[j] = true, dis[j] = dis[i] + 1; 
            dfs(a + 1, tmp + dis[j] * G[i][j]);
            vis[j] = false, dis[j] = 0;
        }
    }
}

void clean() {
    ans = 1000000000, ms(vis, 0);
    for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++) G[i][j] = 1000000000;
}
int solve() {
    clean();
    for (int x, y, w, i = 1; i <= m; i++) scanf("%d%d%d", &x, &y, &w), G[x][y] = std::min(G[x][y], w), G[y][x] = std::min(G[y][x], w);
    for (int i = 1; i <= n; i++) vis[i] = true, dis[i] = 0, dfs(2, 0), vis[i] = false;
    printf("%d\n", ans);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}
------ 本文结束 ------