Codeforces 1005F(最短路树+DFS)

Codeforces 1005F
题意:给你一个$n$个点$m$条边的无向图,要你选出$n-1$条边。你要在其中找到$k$种方案使得图连通并且 1 点到所有其他点距离之和最短。不足 $k$ 种就输出所有方案。

本题运用了最短路树的知识,最短路树就是一个点到其他点最短路的边组成的树。这个树可能有很多个。构造树的方法就是用最短路算法松弛时如果发现最短路相等,那么这里就有两条边可选进最短路树。
这里边权都是1,直接 BFS 。然后 DFS 每个点选一条边进最短路树即可,注意这里可能数组开不下,vector.resize() 就排上用场了。

知识点:
1 求最短路树长度相等时不要再入队, 否则计数会有重边
2 要记得删除调试输出
3 vector.resize() 的绝妙之处

#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 = 200000 + 5;

struct data {int u, dis;};
struct edge {int v, ith, nxt;} ed[MAXN * 2];

int n, m, k, en, hd[MAXN], vis[MAXN], cnt, now[MAXN], fl;
std::vector<int > pre[MAXN];
std::vector<int > ans[MAXN];
std::queue<data > q;

inline void ins(int x, int y, int ith) {
    ed[++en] = (edge){y, ith, hd[x]}, hd[x] = en;
    ed[++en] = (edge){x, ith, hd[y]}, hd[y] = en;
}
void dfs(int a) {
    if (fl == 1) return ;
    if (a == n + 1) {
        ans[++cnt].resize(m + 1);
        for (int i = 0; i < m; i++) ans[cnt][i] = now[i + 1];
        if (cnt == k) fl = 1;
        return ;
    }
    for (int i = 0; i < (int)pre[a].size(); i++) {
        int no = pre[a][i];
        now[no] = 1, dfs(a + 1), now[no] = 0;
        if (fl == 1) return ;
    }
}

void clean() {
    en = 0, ms(hd, -1), ms(vis, 0);
}
int solve() {
    clean();
    for (int a, b, i = 1; i <= m; ++i) scanf("%d%d", &a, &b), ins(a, b, i);
    vis[1] = 1, q.push((data){1, 0});
    while (!q.empty()) {
        data p = q.front(); q.pop();
        for (int i = hd[p.u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (!vis[e.v]) {
                pre[e.v].push_back(e.ith);
                q.push((data){e.v, p.dis + 1}), vis[e.v] = p.dis + 1;
            } else if (vis[e.v] == p.dis + 1) pre[e.v].push_back(e.ith);
        }
    }
    /*for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (int)pre[i].size(); j++) printf("%d ", pre[i][j]);
        printf("\n");
    }*/
    ms(now, 0);
    fl = 0, dfs(2);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j < m; ++j) printf("%d", ans[i][j]);
        printf("\n");
    }
    return 0; 
}
int main() {
    scanf("%d%d%d", &n, &m, &k), solve();
    return 0;
}
------ 本文结束 ------