->点我进原题
-> 7-1 连通分量
-> 7-2 整数拆分
-> 7-3 数字变换
-> 7-4 旅行 I
7-1 连通分量 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(200 ms\)
内存限制 \(10 MB\)
Description
无向图 \(G\) 有 \(n\) 个顶点和 \(m\) 条边。求 \(G\) 的连通分量的数目。
Input
第1行，2个整数 \(n\) 和 \(m\)，用空格分隔，分别表示顶点数和边数， \(1≤n≤50000\)， \(1≤m≤100000\).
第2到m+1行，每行两个整数 \(u\) 和 \(v\)，用空格分隔，表示顶点 \(u\) 到顶点 \(v\) 有一条边，\(u\) 和 \(v\) 是顶点编号，\(1≤u,v≤n\).
Output
1行，1个整数，表示所求连通分量的数目。
Sample Input
6 5
1 3
1 2
2 3
4 5
5 6
Sample Output
2
思路
并查集裸题，每个连通分量代表一个团体，建边即为将两点并入一个团体，团体数即为所求连通分量的数目。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
int f[100010], cnt = 0;
inline int find(rg int v){
return f[v] == v ? v : f[v] = find(f[v]);
}
inline bool merge(rg int x, rg int y){
int f1 = find(x);
int f2 = find(y);
if(f1 != f2){
f[f2] = f1;
return true;
}
return false;
}
signed main(){
int n = read(), m = read();
for(rg int i = 1; i <= n; ++i) f[i] = i;
cnt = n;
for(rg int i = 1; i <= m; ++i){
int u = read(), v = read();
if(merge(u, v)){
cnt --;
}
}
printf("%d", cnt);
return 0;
}
7-2 整数拆分 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(1 MB\)
Description
整数拆分是一个古老又有趣的问题。请给出将正整数 \(n\) 拆分成 \(k\) 个正整数的所有不重复方案。例如，将 \(5\) 拆分成 \(2\) 个正整数的不重复方案，有如下 \(2\) 组：\((1，4)\) 和 \((2，3)\)。注意 \((1，4)\) 和 \((4，1)\) 被视为同一方案。每种方案按递增序输出，所有方案按方案递增序输出。
Input
1行，2个整数 \(n\) 和 \(k\)，用空格分隔， \(1≤k≤n≤50\).
Output
若干行，每行一个拆分方案，方案中的数用空格分隔。
最后一行，给出不同拆分方案的总数。
Sample Input
5 2
Sample Output
1 4
2 3
2
思路
dfs。dfs中定义三个数 \(rem\) 代表当前拆分后剩下的，\(lev\) 代表已经拆分了几个，\(up\) 代表上一次拆分的值，每次递归查找从 \(up\) 一直枚举到 \(rem\) 以保证结果递增，当 \(lev\) 为 \(k\) 且 \(rem\) 恰为 \(0\) 时拆分完毕，注意特判 \(k>n\) 时方案为 \(0\)，\(k=1\) 时只有 \(1\) 种拆分方案为 \(n\)。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
int f[100], n, k, ans = 0;
inline void dfs(rg int rem, rg int lev, rg int up){
if(lev == k && rem == 0){
ans ++;
for(rg int i = 1; i <= k; ++i){
printf("%d", f[i]);
if(i != k) printf(" ");
else printf("\n");
}
}
for(rg int i = up; i <= rem; ++i){
f[lev + 1] = i;
dfs(rem - i, lev + 1, i);
}
}
signed main(){
n = read(), k = read();
if(k > n){
printf("0");
return 0;
}
if(k == 1){
printf("%d\n1", n);
return 0;
}
dfs(n, 0, 1);
printf("%d", ans);
return 0;
}
7-3 数字变换 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(5 MB\)
Description
利用变换规则，一个数可以变换成另一个数。变换规则如下：（1）\(x\) 变为 \(x+1\)；（2）\(x\) 变为 \(2x\)；（3）\(x\) 变为 \(x-1\)。给定两个数 \(x\) 和 \(y\)，至少经过几步变换能让 \(x\) 变换成 \(y\).
Input
1行，2个整数 \(x\) 和 \(y\)，用空格分隔， \(1≤x,y≤100000\).
Output
第1行，1个整数 \(s\)，表示变换的最小步数。
第2行，\(s\) 个数，用空格分隔，表示最少变换时每步变换的结果。规则使用优先级顺序: （1），（2），（3）。
Sample Input
2 14
Sample Output
4
3 6 7 14
思路
bfs。对于一个数 \(x\)，他所能达到的位置就是 \(x+1\)、\(2x\)、\(x-1\)，维护一个队列，将到达的位置都放入队列，对于每个位置，分别记录他处于第几步 \(f\)，上一步的位置 \(step\)，并打上标记 \(vis\)（因为对于以后通过其他位置再次到达该位置时，所得到的步数只可能大于等于当前步数，而我们要的是最小步数，所以对于访问过的位置就可以不再入队），一直找可以遍历到的位置直到找到 \(y\) 即可 \(f[y]\) 即为最小步数，再倒序查找 \(step\) 即可输出路径。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
int f[100010], x, y, step[100010], ans[100010], tot = 0;
int vis[100010] = {0};
queue<int> q;
inline void bfs(){
while(!q.empty()){
int u = q.front();
q.pop();
if(u == y){
return ;
}
if(!vis[u + 1] && u + 1 <= 100000 && u + 1 >= 1){
vis[u + 1] = 1;
q.push(u + 1);
step[u + 1] = u;
f[u + 1] = f[u] + 1;
}
if(!vis[u * 2] && u * 2 <= 100000 && u * 2 >= 1){
vis[u * 2] = 1;
q.push(u * 2);
step[u * 2] = u;
f[u * 2] = f[u] + 1;
}
if(!vis[u - 1] && u - 1 <= 100000 && u - 1 >= 1){
vis[u - 1] = 1;
q.push(u - 1);
step[u - 1] = u;
f[u - 1] = f[u] + 1;
}
}
}
signed main(){
x = read(), y = read();
f[x] = 0;
q.push(x);
step[x] = 0;
vis[x] = 1;
bfs();
int tmp = y;
while(tmp){
ans[++ tot] = tmp;
tmp = step[tmp];
}
printf("%d\n", f[y]);
for(rg int i = f[y]; i >= 1; --i){
printf("%d", ans[i]);
if(i != 1) printf(" ");
}
return 0;
}
7-4 旅行 I (100 分)
代码长度限制 \(16 KB\)
时间限制 \(1000 ms\)
内存限制 \(10 MB\)
Description
五一要到了,来一场说走就走的旅行吧。当然，要关注旅行费用。由于从事计算机专业，你很容易就收集到一些城市之间的交通方式及相关费用。将所有城市编号为1到n，你出发的城市编号是s。你想知道，到其它城市的最小费用分别是多少。如果可能，你想途中多旅行一些城市，在最小费用情况下，到各个城市的途中最多能经过多少城市。
Input
第1行，3个整数 \(n\)、\(m\)、\(s\)，用空格分隔，分别表示城市数、交通方式总数、出发城市编号， \(1≤s≤n≤10000\), \(1≤m≤100000\) 。
第2到m+1行，每行三个整数 \(u\)、\(v\) 和 \(w\)，用空格分隔，表示城市 \(u\) 和城市 \(v\) 的一种双向交通方式费用为 \(w\) ， \(1≤w≤10000\)。
Output
第1行，若干个整数 \(Pi\)，用空格分隔，\(Pi\) 表示 \(s\) 能到达的城市i的最小费用，\(1≤i≤n\)，按城市号递增顺序。
第2行，若干个整数 \(Ci\)，\(Ci\) 表示在最小费用情况下，\(s\) 到城市 \(i\) 的最多经过的城市数， \(1≤i≤n\)，按城市号递增顺序。
Sample Input
5 5 1
1 2 2
1 4 5
2 3 4
3 5 7
4 5 8
Sample Output
0 2 6 5 13
0 1 2 1 3
思路
以一个城市到另一个城市的花费为边权，建图跑SPFA，最短路即为最小费用；同时维护一个经过城市数 \(rd\)，在每次对于松弛与否做判断时，如果松弛后路径变小，则将后一个城市的 \(rd\) 更新为前一个城市的 \(rd+1\)，如果松弛路径相等，则将后一个城市的 \(rd\) 与前一个城市的 \(rd+1\) 取较大值更新即可。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
const int inf = 0x7fffffff;
struct edge{
int nxt, to, val;
}e[200010];
int n, m, s, head[200010], vis[100010], dis[100010], rd[100010];
int tot = 0;
queue<int> q;
inline void add(rg int u, rg int v, rg int w){
e[++tot].nxt = head[u];
e[tot].to = v;
e[tot].val = w;
head[u] = tot;
}
inline void spfa(){
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for(rg int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dis[v] > dis[u] + e[i].val){
dis[v] = dis[u] + e[i].val;
rd[v] = rd[u] + 1;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
} else if(dis[v] == dis[u] + e[i].val){
rd[v] = max(rd[v], rd[u] + 1);
}
}
}
}
signed main(){
n = read(); m = read(); s = read();
for(rg int i = 1; i <= m; ++i){
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
for(rg int i = 1; i <= n; ++i) dis[i] = inf, vis[i] = 0, rd[i] = 0;
dis[s] = 0;
q.push(s);
spfa();
for(rg int i = 1; i <= n; ++i){
printf("%d", dis[i]);
if(i != n) printf(" ");
else printf("\n");
}
for(rg int i = 1; i <= n; ++i){
printf("%d", rd[i]);
if(i != n) printf(" ");
}
return 0;
}