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;
}