842. 排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 10;
  7. bool st[N];
  8. int a[N];
  9. int n;
  10. void dfs(int index){
  11.     if(index==n){
  12.         for (int i = 0; i < n; i ++ ){
  13.             cout << a[i] <<" ";
  14.         }
  15.         cout << endl;
  16.         return ;
  17.     }
  18.     for (int i = 1; i <= n; i ++ ){
  19.         if(!st[i]){
  20.             a[index] = i;
  21.             st[i] = true;
  22.             dfs(index+1);
  23.             st[i] = false;
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin >> n;
  30.     dfs(0);
  31. }

树与图的广度优先遍历

847. 图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  6. #define x first
  7. #define y second
  9. using namespace std;
  10. const int N = 1e5+10;
  11. typedef pair<int, int> PII;
  12. vector<int>h[N];
  13. bool st[N];
  15. void bfs(int u,int v){// 从u节点开始找v
  16.     queue<PII>q;
  17.     q.push({u,0}); // 节点距离
  18.     st[u] = true;
  20.     if(u==v){  // 这块必须加，不然会出错 看上面得样例
  21.         cout << 0 <<endl;
  22.         return ;
  23.     }
  24.     while(!q.empty()){
  25.         auto t = q.front();
  26.         q.pop();
  27.         int a = t.x;
  28.         int d = t.y;
  29.         for (int i = 0; i < h[a].size(); i ++ ){
  30.             int j = h[a][i];
  31.             if(j==v){
  32.                 cout << d+1 <<endl;
  33.                 return ;
  34.             }
  35.             if(!st[j]){
  36.                 q.push({j,d+1});
  37.                 st[j] = true;
  38.             }
  39.         }
  40.     }
  41.     cout << -1 <<endl;
  43. }
  44. int main()
  45. {
  46.     int n,m;
  47.     cin >> n >> m;
  48.     for (int i = 0; i < m; i ++ ){
  49.         int a,b;
  50.         cin >> a >> b;
  51.         h[a].push_back(b);
  52.     }
  53.     bfs(1,n);
  54. }

拓扑排序

848. 有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  7. using namespace std;
  8. const int N = 1e5+10;
  9. int d[N];
  10. vector<int>h[N];
  11. vector<int>res;
  12. bool st[N];
  13. int n,m;
  15. void topsort(){
  16.     queue<int>q;
  17.     for (int i = 1; i <= n; i ++ ){
  18.         if(!d[i]){
  19.             q.push(i);
  20.             st[i] = true;
  21.         }
  22.     }
  23.     while(!q.empty()){
  24.         auto t = q.front();
  25.         q.pop();
  26.         res.push_back(t);
  27.         for (int i = 0; i < h[t].size(); i ++ ){
  28.             int j = h[t][i];
  29.             if(st[j]){
  30.                 continue;
  31.             }
  32.             d[j]--;
  33.             if(d[j]<=0){
  34.                 q.push(j);
  35.                 st[j] = true;
  36.             }
  37.         }
  38.     }
  39.     if(res.size()<n){
  40.         cout << -1 <<endl;
  41.     }else{
  42.         for(auto t:res){
  43.             cout << t<<" ";
  44.         }
  45.     }
  46. }
  48. int main()
  49. {
  50.     cin >> n >> m;
  51.     for (int i = 0; i < m; i ++ ){
  52.         int a,b;
  53.         cin >> a >> b;
  54.         h[a].push_back(b);
  55.         d[b]++;
  56.     }
  57.     topsort();
  58. }

Dijkstra

image.png

849. Dijkstra求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
image.png

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 510;
  9. int n, m;
  10. int g[N][N];
  11. int dist[N];
  12. bool st[N];
  14. int dijkstra()
  15. {
  16.     memset(dist, 0x3f, sizeof dist);
  17.     memset(st, 0x3f, sizeof st);
  18.     dist[1] = 0;
  20.     for (int i = 0; i < n - 1; i ++ )  // 这里是n-1次
  21.     {
  22.         int t = -1;
  23.         for (int j = 1; j <= n; j ++ )
  24.             if (!st[j] && (t == -1 || dist[t] > dist[j]))
  25.                 t = j;
  27.         for (int j = 1; j <= n; j ++ )
  28.             dist[j] = min(dist[j], dist[t] + g[t][j]);
  30.         st[t] = true;
  31.     }
  33.     if (dist[n] == 0x3f3f3f3f) return -1;
  34.     return dist[n];
  35. }
  37. int main()
  38. {
  39.     scanf("%d%d", &n, &m);
  41.     memset(g, 0x3f, sizeof g);
  42.     while (m -- )
  43.     {
  44.         int a, b, c;
  45.         scanf("%d%d%d", &a, &b, &c);
  47.         g[a][b] = min(g[a][b], c);
  48.     }
  50.     printf("%d\n", dijkstra());
  52.     return 0;
  53. }

850. Dijkstra求最短路 II(堆优化版)

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×10^5,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  7. #define x first
  8. #define y second
  10. using namespace std;
  12. typedef pair<int, int> PII;
  13. const int N = 510;
  14. vector<PII>h[N];
  15. int n,m;
  16. int dist[N];
  17. bool st[N];
  19. int dij(){
  20.     memset(dist,0x3f,sizeof dist);
  21.     dist[1] = 0;
  22.     priority_queue<PII,vector<PII>,greater<PII>>heap;
  23.     heap.push({0,1});
  24.     while(!heap.empty()){
  25.         auto t=heap.top();
  26.         heap.pop();
  28.         int ver = t.y;
  29.         int d1 = t.x;
  30.         if(st[ver]){
  31.             continue;
  32.         }
  33.         // 只能在这里标记访问，和dij类似，只有从队列出来，这个点的路径才是最短路
  34.         st[ver] = true;
  35.         for (int i = 0; i < h[ver].size(); i ++ ){
  36.             int son = h[ver][i].x;
  37.             int d2 = h[ver][i].y;
  38.             if(st[son]){
  39.                 continue;
  40.             }
  41.             if(d1 + d2 < dist[son]){
  42.                 dist[son] = d1+d2;
  43.                 heap.push({d1+d2,son});
  44.             }
  45.         }
  46.     }
  48.     if(dist[n]==0x3f3f3f3f){
  49.         return -1;
  50.     }
  51.     return dist[n];
  52. }
  54. int main()
  55. {
  56.     cin >> n >> m;
  57.     for (int i = 0; i < m; i ++ ){
  58.         int a,b,c;
  59.         cin >> a >> b >> c;
  60.         h[a].push_back({b,c});
  61.     }
  62.     cout << dij() <<endl;
  63. }

bellman-ford

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
image.png
image.png
image.png

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 510, M = 10010;
  9. struct Edge
  10. {
  11.     int a, b, c;
  12. }edges[M];
  14. int n, m, k;
  15. int dist[N];
  16. int last[N];
  18. void bellman_ford()
  19. {
  20.     memset(dist, 0x3f, sizeof dist);
  22.     dist[1] = 0;
  23.     for (int i = 0; i < k; i ++ )
  24.     {
  25.         memcpy(last, dist, sizeof dist);
  26.         for (int j = 0; j < m; j ++ )
  27.         {
  28.             auto e = edges[j];
  29.             dist[e.b] = min(dist[e.b], last[e.a] + e.c);
  30.         }
  31.     }
  32. }
  34. int main()
  35. {
  36.     scanf("%d%d%d", &n, &m, &k);
  38.     for (int i = 0; i < m; i ++ )
  39.     {
  40.         int a, b, c;
  41.         scanf("%d%d%d", &a, &b, &c);
  42.         edges[i] = {a, b, c};
  43.     }
  45.     bellman_ford();
  47.     if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
  48.     else printf("%d\n", dist[n]);
  50.     return 0;
  51. }

spfa

851. spfa求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤10^5,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  7. #define x first
  8. #define y second
  10. using namespace std;
  12. typedef pair<int, int> PII;
  13. const int N = 1e5+10;
  14. vector<PII>h[N];
  15. int n,m;
  16. int dist[N];
  17. bool st[N];
  19. void spfa(){
  20.     memset(dist, 0x3f, sizeof dist);
  21.     dist[1] = 0;
  22.     queue<int>q;
  23.     q.push(1);
  24.     while(!q.empty()){
  25.         int a = q.front();
  26.         st[a] = false;
  27.         q.pop();
  28.         for (int i = 0; i < h[a].size(); i ++ ){
  29.             int b = h[a][i].x;
  30.             int c = h[a][i].y;
  31.             int t = dist[a]+c;
  32.             if(t<dist[b]){
  33.                 dist[b] = t;
  34.                 if(!st[b]){
  35.                     q.push(b);
  36.                     st[b] = true;
  37.                 }
  38.             }
  39.         }
  40.     }
  41. }
  43. int main()
  44. {
  45.     cin >> n >> m;
  46.     while (m -- ){
  47.         int a,b,c;
  48.         cin >> a >> b >> c;
  49.         h[a].push_back({b,c});
  50.     }
  51.     spfa();
  52.     if(dist[n]==0x3f3f3f3f){
  53.         puts("impossible");
  54.     }else{
  55.         cout << dist[n];
  56.     }
  57. }

852. spfa判断负环

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  7. #define x first
  8. #define y second
  10. using namespace std;
  12. typedef pair<int, int> PII;
  13. const int N = 1e5+10;
  14. vector<PII>h[N];
  15. int n,m;
  16. int dist[N],cnt[N];
  17. bool st[N];
  19. bool spfa(){
  20.     queue<int>q;
  21.     //因为不一定是1号点开始得负环，所以把所有点都加进来
  22.     for (int i = 1; i <= n; i ++ ){
  23.         q.push(i);
  24.     }
  25.     // dist也不需要初始化，反正只要到一个点得边大于等于n肯定存在负环
  26.     while(!q.empty()){
  27.         int a = q.front();
  28.         st[a] = false;
  29.         q.pop();
  30.         for (int i = 0; i < h[a].size(); i ++ ){
  31.             int b = h[a][i].x;
  32.             int c = h[a][i].y;
  33.             int t = dist[a]+c;
  34.             if(t<dist[b]){
  35.                 dist[b] = t;
  36.                 cnt[b] = cnt[a]+1;
  37.                 if(cnt[b]>=n){
  38.                     return true;
  39.                 }
  40.                 if(!st[b]){
  41.                     q.push(b);
  42.                     st[b] = true;
  43.                 }
  44.             }
  45.         }
  46.     }
  47.     return false;
  48. }
  50. int main()
  51. {
  52.     cin >> n >> m;
  53.     while (m -- ){
  54.         int a,b,c;
  55.         cin >> a >> b >> c;
  56.         h[a].push_back({b,c});
  57.     }
  59.     if(spfa()){
  60.         puts("Yes");
  61.     }else{
  62.         puts("No");
  63.     }
  64. }

854. Floyd求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<vector>
  5. #define x first
  6. #define y second
  7. using namespace std;
  8. const int N =210;
  10. int g[N][N];
  11. int n,m,K;
  13. int main(){
  14.     cin >> n >> m >> K;
  15.     memset(g,0x3f,sizeof g);
  16.     for(int i=0;i<m;i++){
  17.         int a,b,c;
  18.         cin >> a >> b >> c;
  19.         g[a][b]=min(g[a][b],c); // 存在重边得处理
  20.     }
  22.     for(int k=1;k<=n;k++){
  23.         for(int i=1;i<=n;i++){
  24.             g[i][i]=0;  // 这块得初始化
  25.             for(int j=1;j<=n;j++){
  26.                 g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
  27.             }
  28.         }
  29.     }
  30.     while(K--){
  31.         int a,b;
  32.         cin >> a >> b;
  33.         if(g[a][b]>=0x3f3f3f3f/2){  // 有负边
  34.             puts("impossible");
  35.         }else
  36.         cout<<g[a][b]<<endl;
  37.     }
  38.     return 0;
  39. }

Prim

858. Prim算法求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 510,INF = 0x3f3f3f3f;
  7. int g[N][N];
  8. int dist[N];
  9. bool st[N];
  10. int n,m;
  11. int res;
  12. void prim(){
  13.     dist[1]=0;
  14.     for (int i = 0; i < n; i ++ ){ // 这里是n次
  15.         int t=-1;
  16.         for (int j = 1; j <= n; j ++ ){
  17.             if(!st[j]&&(t==-1||dist[j]<dist[t])){
  18.                 t = j;
  19.             }
  20.         }
  21.         if(dist[t]==INF){ // 表明这个图不是连通图
  22.             res = INF;
  23.             return ;
  24.         }
  25.         res += dist[t];
  26.         st[t] = true;
  27.         for (int i = 1; i <= n; i ++ ){
  28.             dist[i] = min(dist[i],g[t][i]);
  29.         }
  30.     }
  31. }
  33. int main()
  34. {
  35.     cin >> n >> m;
  36.     memset(dist,0x3f,sizeof dist);
  37.     memset(g,0x3f,sizeof g);
  38.     while (m -- ){
  39.         int a,b,c;
  40.         cin >> a >> b >> c;
  41.         g[a][b] = min(g[a][b],c); // 处理存在重边的问题
  42.         g[b][a] = min(g[b][a],c);
  43.     }
  44.     prim();
  45.     if(res==INF){
  46.         puts("impossible");
  47.     }else{
  48.         cout << res;
  49.     }
  50. }

859. Kruskal算法求最小生成树

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 2e5+10;
  8. struct Edge{
  9.     int a,b,c;
  10.     bool operator<(const Edge t)const{
  11.         return c<t.c;
  12.     }
  13. }g[N];
  14. int n,m,cnt,res;
  15. int p[N];
  17. int find(int x){
  18.     if(p[x]!=x){
  19.         p[x] = find(p[x]);
  20.     }
  21.     return p[x];
  22. }
  24. int kruskal(){
  26.     for (int i = 1; i <= n; i ++ ){
  27.         p[i] = i;
  28.     }
  29.     sort(g,g+m);
  30.     for (int i = 0; i < m; i ++ ){
  31.         int pa = find(g[i].a);
  32.         int pb = find(g[i].b);
  33.         if(pa==pb){
  34.             continue;
  35.         }
  36.         res+=g[i].c;
  37.         cnt++;
  38.         p[pa]=pb;
  39.     }
  40. }
  42. int main()
  43. {
  44.     cin >> n >> m;
  45.     for (int i = 0; i < m; i ++ ){
  46.         cin >> g[i].a >> g[i].b >> g[i].c;
  47.     }
  48.     kruskal();
  49.     if(cnt<n-1){
  50.         puts("impossible");
  51.     }else{
  52.         cout << res;
  53.     }
  54. }

染色法判定二分图