• 【算法笔记自学】第 10 章 提高篇（4）——图算法专题

    10.1图的定义和相关术语

    1. #include 
    2.  
    3. const int MAXN = 100;
    4. int degree[MAXN] = {0};
    5.  
    6. int main() {
    7.     int n, m, u, v;
    8.     scanf("%d%d", &n, &m);
    9.     for (int j = 0; j < m; j++) {
    10.         scanf("%d%d", &u, &v);
    11.         degree[u]++;
    12.         degree[v]++;
    13.     }
    14.     for (int i = 0; i < n; i++) {
    15.         printf("%d", degree[i]);
    16.         if (i < n - 1) {
    17.             printf(" ");
    18.         }
    19.     }
    20.     return 0;
    21. }

    1. #include 
    2.  
    3. const int MAXN = 100;
    4. int inDegree[MAXN] = {0};
    5. int outDegree[MAXN] = {0};
    6.  
    7. int main() {
    8.     int n, m, u, v;
    9.     scanf("%d%d", &n, &m);
    10.     for (int j = 0; j < m; j++) {
    11.         scanf("%d%d", &u, &v);
    12.         outDegree[u]++;
    13.         inDegree[v]++;
    14.     }
    15.     for (int i = 0; i < n; i++) {
    16.         printf("%d %d\n", inDegree[i], outDegree[i]);
    17.     }
    18.     return 0;
    19. }

    10.2图的存储

    1. #include 
    2. #include 
    3.  
    4. const int MAXN = 100;
    5. int G[MAXN][MAXN];
    6.  
    7. int main() {
    8.     memset(G, 0, sizeof(G));
    9.     int n, m, u, v;
    10.     scanf("%d%d", &n, &m);
    11.     for (int i = 0; i < m; i++) {
    12.         scanf("%d%d", &u, &v);
    13.         G[u][v] = G[v][u] = 1;
    14.     }
    15.     for (int i = 0; i < n; i++) {
    16.         for (int j = 0; j < n; j++) {
    17.             printf("%d", G[i][j]);
    18.             printf(j < n - 1 ? " " : "\n");
    19.         }
    20.     }
    21.     return 0;
    22. }

    1. #include 
    2. #include 
    3.  
    4. const int MAXN = 100;
    5. int G[MAXN][MAXN];
    6.  
    7. int main() {
    8.     memset(G, 0, sizeof(G));
    9.     int n, m, u, v;
    10.     scanf("%d%d", &n, &m);
    11.     for (int i = 0; i < m; i++) {
    12.         scanf("%d%d", &u, &v);
    13.         G[u][v] = 1;
    14.     }
    15.     for (int i = 0; i < n; i++) {
    16.         for (int j = 0; j < n; j++) {
    17.             printf("%d", G[i][j]);
    18.             printf(j < n - 1 ? " " : "\n");
    19.         }
    20.     }
    21.     return 0;
    22. }

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int MAXN = 100;
    6. vector<int> G[MAXN];
    7.  
    8. int main() {
    9.     int n, m, u, v;
    10.     scanf("%d%d", &n, &m);
    11.     for (int i = 0; i < m; i++) {
    12.         scanf("%d%d", &u, &v);
    13.         G[u].push_back(v);
    14.         G[v].push_back(u);
    15.     }
    16.     for (int i = 0; i < n; i++) {
    17.         printf("%d(%d)", i, (int)G[i].size());
    18.         for (int j = 0; j < G[i].size(); j++) {
    19.             printf(" %d", G[i][j]);
    20.         }
    21.         printf("\n");
    22.     }
    23.     return 0;
    24. }

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int MAXN = 100;
    6. vector<int> G[MAXN];
    7.  
    8. int main() {
    9.     int n, m, u, v;
    10.     scanf("%d%d", &n, &m);
    11.     for (int i = 0; i < m; i++) {
    12.         scanf("%d%d", &u, &v);
    13.         G[u].push_back(v);
    14.     }
    15.     for (int i = 0; i < n; i++) {
    16.         printf("%d(%d)", i, (int)G[i].size());
    17.         for (int j = 0; j < G[i].size(); j++) {
    18.             printf(" %d", G[i][j]);
    19.         }
    20.         printf("\n");
    21.     }
    22.     return 0;
    23. }

    10.3图的遍历

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int MAXN = 100;
    7. vector<int> G[MAXN];
    8. bool vis[MAXN];
    9.  
    10. void DFS(int u) {
    11.     vis[u] = true;
    12.     for (int i = 0; i < G[u].size(); i++) {
    13.         int v = G[u][i];
    14.         if (!vis[v]) {
    15.             DFS(v);
    16.         }
    17.     }
    18. }
    19.  
    20. int main() {
    21.     memset(vis, false, sizeof(vis));
    22.     int n, m, u, v;
    23.     scanf("%d%d", &n, &m);
    24.     for (int i = 0; i < m; i++) {
    25.         scanf("%d%d", &u, &v);
    26.         G[u].push_back(v);
    27.         G[v].push_back(u);
    28.     }
    29.     int blockCount = 0;
    30.     for (int i = 0; i < n; i++) {
    31.         if (!vis[i]) {
    32.             DFS(i);
    33.             blockCount++;
    34.         }
    35.     }
    36.     printf("%d", blockCount);
    37.     return 0;
    38. }

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int MAXN = 100;
    7. vector<int> G[MAXN];
    8. bool vis[MAXN];
    9.  
    10. void DFS(int u) {
    11.     vis[u] = true;
    12.     for (int i = 0; i < G[u].size(); i++) {
    13.         int v = G[u][i];
    14.         if (!vis[v]) {
    15.             DFS(v);
    16.         }
    17.     }
    18. }
    19.  
    20. int main() {
    21.     memset(vis, false, sizeof(vis));
    22.     int n, m, u, v;
    23.     scanf("%d%d", &n, &m);
    24.     for (int i = 0; i < m; i++) {
    25.         scanf("%d%d", &u, &v);
    26.         G[u].push_back(v);
    27.         G[v].push_back(u);
    28.     }
    29.     int blockCount = 0;
    30.     for (int i = 0; i < n; i++) {
    31.         if (!vis[i]) {
    32.             DFS(i);
    33.             blockCount++;
    34.         }
    35.     }
    36.     printf(blockCount == 1 ? "Yes" : "No");
    37.     return 0;
    38. }

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int MAXN = 100;
    7. vector<int> G[MAXN];
    8. int vis[MAXN];
    9.  
    10. bool isCyclic(int u) {
    11.     vis[u] = 0;
    12.     for (int i = 0; i < G[u].size(); i++) {
    13.         int v = G[u][i];
    14.         if (vis[v] == -1 && isCyclic(v)) {
    15.             return true;
    16.         } else if (vis[v] == 0) {
    17.             return true;
    18.         }
    19.     }
    20.     vis[u] = 1;
    21.     return false;
    22. }
    23.  
    24. int main() {
    25.     memset(vis, -1, sizeof(vis));
    26.     int n, m, u, v;
    27.     scanf("%d%d", &n, &m);
    28.     for (int i = 0; i < m; i++) {
    29.         scanf("%d%d", &u, &v);
    30.         G[u].push_back(v);
    31.     }
    32.     int isCyclicResult = false;
    33.     for (int i = 0; i < n; i++) {
    34.         if (vis[i] == -1 && isCyclic(i)) {
    35.             isCyclicResult = true;
    36.         }
    37.         if (isCyclicResult) {
    38.             break;
    39.         }
    40.     }
    41.     printf(isCyclicResult ? "Yes" : "No");
    42.     return 0;
    43. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. int weight[MAXN];
    9. vector<int> G[MAXN];
    10. bool vis[MAXN];
    11.  
    12. int DFS(int u) {
    13.     vis[u] = true;
    14.     int weightSum = weight[u];
    15.     for (int i = 0; i < G[u].size(); i++) {
    16.         int v = G[u][i];
    17.         if (!vis[v]) {
    18.             weightSum += DFS(v);
    19.         }
    20.     }
    21.     return weightSum;
    22. }
    23.  
    24. int main() {
    25.     memset(vis, false, sizeof(vis));
    26.     int n, m, u, v;
    27.     scanf("%d%d", &n, &m);
    28.     for (int i = 0; i < n; i++) {
    29.         scanf("%d", &weight[i]);
    30.     }
    31.     for (int i = 0; i < m; i++) {
    32.         scanf("%d%d", &u, &v);
    33.         G[u].push_back(v);
    34.         G[v].push_back(u);
    35.     }
    36.     int maxWeightSum = 0;
    37.     for (int i = 0; i < n; i++) {
    38.         if (!vis[i]) {
    39.             maxWeightSum = max(maxWeightSum, DFS(i));
    40.         }
    41.     }
    42.     printf("%d", maxWeightSum);
    43.     return 0;
    44. }

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int MAXN = 100;
    7. vector<int> G[MAXN];
    8. bool inQueue[MAXN] = {false};
    9. int layers[MAXN];
    10.  
    11. void BFS(int s) {
    12.     queue<int> q;
    13.     q.push(s);
    14.     inQueue[s] = true;
    15.     int layer = 0;
    16.     while (!q.empty()) {
    17.         int cnt = q.size();
    18.         for (int i = 0; i < cnt; i++) {
    19.             int front = q.front();
    20.             q.pop();
    21.             layers[front] = layer;
    22.             for (int j = 0; j < G[front].size(); j++) {
    23.                 int v = G[front][j];
    24.                 if (!inQueue[v]) {
    25.                     q.push(v);
    26.                     inQueue[v] = true;
    27.                 }
    28.             }
    29.         }
    30.         layer++;
    31.     }
    32. }
    33.  
    34. int main() {
    35.     int n, m, start, u, v;
    36.     scanf("%d%d%d", &n, &m, &start);
    37.     for (int i = 0; i < m; i++) {
    38.         scanf("%d%d", &u, &v);
    39.         G[u].push_back(v);
    40.         G[v].push_back(u);
    41.     }
    42.     BFS(start);
    43.     for (int i = 0; i < n; i++) {
    44.         printf("%d", layers[i]);
    45.         if (i < n - 1) {
    46.             printf(" ");
    47.         }
    48.     }
    49.     return 0;
    50. }

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int MAXN = 100;
    7. vector<int> G[MAXN];
    8. bool inQueue[MAXN] = {false};
    9.  
    10. int BFS(int s, int maxLayer) {
    11.     queue<int> q;
    12.     q.push(s);
    13.     inQueue[s] = true;
    14.     int layer = 0;
    15.     int vertexCount = 0;
    16.     while (!q.empty() && layer <= maxLayer) {
    17.         int cnt = q.size();
    18.         vertexCount += cnt;
    19.         for (int i = 0; i < cnt; i++) {
    20.             int front = q.front();
    21.             q.pop();
    22.             for (int j = 0; j < G[front].size(); j++) {
    23.                 int v = G[front][j];
    24.                 if (!inQueue[v]) {
    25.                     q.push(v);
    26.                     inQueue[v] = true;
    27.                 }
    28.             }
    29.         }
    30.         layer++;
    31.     }
    32.     return vertexCount;
    33. }
    34.  
    35. int main() {
    36.     int n, m, start, maxLayer, u, v;
    37.     scanf("%d%d%d%d", &n, &m, &start, &maxLayer);
    38.     for (int i = 0; i < m; i++) {
    39.         scanf("%d%d", &u, &v);
    40.         G[u].push_back(v);
    41.     }
    42.     int vertexCount = BFS(start, maxLayer);
    43.     printf("%d", vertexCount);
    44.     return 0;
    45. }

    10.4最短路径

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis;
    12.     Edge(int _v, int _dis) {
    13.         v = _v, dis = _dis;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN];
    19. bool vis[MAXN];
    20.  
    21. void dijkstra(int n, int s) {
    22.     fill(d, d + MAXN, INF);
    23.     memset(vis, false, sizeof(vis));
    24.     d[s] = 0;
    25.     for (int i = 0; i < n; i++) {
    26.         int u = -1, minDis = INF;
    27.         for (int j = 0; j < n; j++) {
    28.             if (!vis[j] && d[j] < minDis) {
    29.                 u = j;
    30.                 minDis = d[j];
    31.             }
    32.         }
    33.         if (u == -1) {
    34.             return;
    35.         }
    36.         vis[u] = true;
    37.         for (int j = 0; j < G[u].size(); j++) {
    38.             int v = G[u][j].v;
    39.             int dis = G[u][j].dis;
    40.             if (!vis[v] && d[u] + dis < d[v]) {
    41.                 d[v] = d[u] + dis;
    42.             }
    43.         }
    44.     }
    45. }
    46.  
    47. int main() {
    48.     int n, m, s, t;
    49.     scanf("%d%d%d%d", &n, &m, &s, &t);
    50.     int u, v, w;
    51.     for (int i = 0; i < m; i++) {
    52.         scanf("%d%d%d", &u, &v, &w);
    53.         G[u].push_back(Edge(v, w));
    54.         G[v].push_back(Edge(u, w));
    55.     }
    56.     dijkstra(n, s);
    57.     if (d[t] == INF) {
    58.         printf("-1");
    59.     } else {
    60.         printf("%d", d[t]);
    61.     }
    62.     return 0;
    63. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis;
    12.     Edge(int _v, int _dis) {
    13.         v = _v, dis = _dis;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN];
    19. bool vis[MAXN];
    20.  
    21. void dijkstra(int n, int s) {
    22.     fill(d, d + MAXN, INF);
    23.     memset(vis, false, sizeof(vis));
    24.     d[s] = 0;
    25.     for (int i = 0; i < n; i++) {
    26.         int u = -1, minDis = INF;
    27.         for (int j = 0; j < n; j++) {
    28.             if (!vis[j] && d[j] < minDis) {
    29.                 u = j;
    30.                 minDis = d[j];
    31.             }
    32.         }
    33.         if (u == -1) {
    34.             return;
    35.         }
    36.         vis[u] = true;
    37.         for (int j = 0; j < G[u].size(); j++) {
    38.             int v = G[u][j].v;
    39.             int dis = G[u][j].dis;
    40.             if (!vis[v] && d[u] + dis < d[v]) {
    41.                 d[v] = d[u] + dis;
    42.             }
    43.         }
    44.     }
    45. }
    46.  
    47. int main() {
    48.     int n, m, s;
    49.     scanf("%d%d%d", &n, &m, &s);
    50.     int u, v, w;
    51.     for (int i = 0; i < m; i++) {
    52.         scanf("%d%d%d", &u, &v, &w);
    53.         G[u].push_back(Edge(v, w));
    54.         G[v].push_back(Edge(u, w));
    55.     }
    56.     dijkstra(n, s);
    57.     for (int i = 0; i < n; i++) {
    58.         if (d[i] == INF) {
    59.             printf("-1");
    60.         } else {
    61.             printf("%d", d[i]);
    62.         }
    63.         if (i < n - 1) {
    64.             printf(" ");
    65.         }
    66.     }
    67.     return 0;
    68. }

     

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis, cost;
    12.     Edge(int _v, int _dis, int _cost) {
    13.         v = _v, dis = _dis, cost = _cost;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN], c[MAXN];
    19. bool vis[MAXN];
    20.  
    21. void dijkstra(int n, int s) {
    22.     fill(d, d + MAXN, INF);
    23.     fill(c, c + MAXN, INF);
    24.     memset(vis, false, sizeof(vis));
    25.     d[s] = 0;
    26.     c[s] = 0;
    27.     for (int i = 0; i < n; i++) {
    28.         int u = -1, minDis = INF;
    29.         for (int j = 0; j < n; j++) {
    30.             if (!vis[j] && d[j] < minDis) {
    31.                 u = j;
    32.                 minDis = d[j];
    33.             }
    34.         }
    35.         if (u == -1) {
    36.             return;
    37.         }
    38.         vis[u] = true;
    39.         for (int j = 0; j < G[u].size(); j++) {
    40.             int v = G[u][j].v;
    41.             int dis = G[u][j].dis;
    42.             int cost = G[u][j].cost;
    43.             if (!vis[v]) {
    44.                 if (d[u] + dis < d[v]) {
    45.                     d[v] = d[u] + dis;
    46.                     c[v] = c[u] + cost;
    47.                 } else if (d[u] + dis == d[v] && c[u] + cost < c[v]) {
    48.                     c[v] = c[u] + cost;
    49.                 }
    50.             }
    51.         }
    52.     }
    53. }
    54.  
    55. int main() {
    56.     int n, m, s, t;
    57.     scanf("%d%d%d%d", &n, &m, &s, &t);
    58.     int u, v, dis, cost;
    59.     for (int i = 0; i < m; i++) {
    60.         scanf("%d%d%d%d", &u, &v, &dis, &cost);
    61.         G[u].push_back(Edge(v, dis, cost));
    62.         G[v].push_back(Edge(u, dis, cost));
    63.     }
    64.     dijkstra(n, s);
    65.     printf("%d %d", d[t], c[t]);
    66.     return 0;
    67. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis;
    12.     Edge(int _v, int _dis) {
    13.         v = _v, dis = _dis;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN], pathCount[MAXN];
    19. bool vis[MAXN];
    20.  
    21. void dijkstra(int n, int s) {
    22.     fill(d, d + MAXN, INF);
    23.     memset(pathCount, 0, sizeof(pathCount));
    24.     memset(vis, false, sizeof(vis));
    25.     d[s] = 0;
    26.     pathCount[s] = 1;
    27.     for (int i = 0; i < n; i++) {
    28.         int u = -1, minDis = INF;
    29.         for (int j = 0; j < n; j++) {
    30.             if (!vis[j] && d[j] < minDis) {
    31.                 u = j;
    32.                 minDis = d[j];
    33.             }
    34.         }
    35.         if (u == -1) {
    36.             return;
    37.         }
    38.         vis[u] = true;
    39.         for (int j = 0; j < G[u].size(); j++) {
    40.             int v = G[u][j].v;
    41.             int dis = G[u][j].dis;
    42.             if (!vis[v]) {
    43.                 if (d[u] + dis < d[v]) {
    44.                     d[v] = d[u] + dis;
    45.                     pathCount[v] = pathCount[u];
    46.                 } else if (d[u] + dis == d[v]) {
    47.                     pathCount[v] += pathCount[u];
    48.                 }
    49.             }
    50.         }
    51.     }
    52. }
    53.  
    54. int main() {
    55.     int n, m, s, t;
    56.     scanf("%d%d%d%d", &n, &m, &s, &t);
    57.     int u, v, w;
    58.     for (int i = 0; i < m; i++) {
    59.         scanf("%d%d%d", &u, &v, &w);
    60.         G[u].push_back(Edge(v, w));
    61.         G[v].push_back(Edge(u, w));
    62.     }
    63.     dijkstra(n, s);
    64.     printf("%d %d", d[t], pathCount[t]);
    65.     return 0;
    66. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis;
    12.     Edge(int _v, int _dis) {
    13.         v = _v, dis = _dis;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN], pre[MAXN];
    19. bool vis[MAXN];
    20.  
    21. void dijkstra(int n, int s) {
    22.     fill(d, d + MAXN, INF);
    23.     memset(pre, -1, sizeof(pre));
    24.     memset(vis, false, sizeof(vis));
    25.     d[s] = 0;
    26.     for (int i = 0; i < n; i++) {
    27.         int u = -1, minDis = INF;
    28.         for (int j = 0; j < n; j++) {
    29.             if (!vis[j] && d[j] < minDis) {
    30.                 u = j;
    31.                 minDis = d[j];
    32.             }
    33.         }
    34.         if (u == -1) {
    35.             return;
    36.         }
    37.         vis[u] = true;
    38.         for (int j = 0; j < G[u].size(); j++) {
    39.             int v = G[u][j].v;
    40.             int dis = G[u][j].dis;
    41.             if (!vis[v] && d[u] + dis < d[v]) {
    42.                 d[v] = d[u] + dis;
    43.                 pre[v] = u;
    44.             }
    45.         }
    46.     }
    47. }
    48.  
    49. vector<int> path;
    50.  
    51. void DFS(int v, int s) {
    52.     if (v == s) {
    53.         path.push_back(v);
    54.         return;
    55.     }
    56.     DFS(pre[v], s);
    57.     path.push_back(v);
    58. }
    59.  
    60. int main() {
    61.     int n, m, s, t;
    62.     scanf("%d%d%d%d", &n, &m, &s, &t);
    63.     int u, v, w;
    64.     for (int i = 0; i < m; i++) {
    65.         scanf("%d%d%d", &u, &v, &w);
    66.         G[u].push_back(Edge(v, w));
    67.         G[v].push_back(Edge(u, w));
    68.     }
    69.     dijkstra(n, s);
    70.     DFS(t, s);
    71.     printf("%d ", d[t]);
    72.     for (int i = 0; i < path.size(); i++) {
    73.         printf("%d", path[i]);
    74.         if (i < (int)path.size() - 1) {
    75.             printf("->");
    76.         }
    77.     }
    78.     return 0;
    79. }

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int MAXN = 50;
    6. const int INF = 1e9;
    7.  
    8. int d[MAXN][MAXN];
    9.  
    10. void floyd(int n) {
    11.     for (int k = 0; k < n; k++) {
    12.         for (int i = 0; i < n; i++) {
    13.             for (int j = 0; j < n; j++) {
    14.                 if (d[i][k] != INF && d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) {
    15.                     d[i][j] = d[i][k] + d[k][j];
    16.                 }
    17.             }
    18.         }
    19.     }
    20. }
    21.  
    22. int main() {
    23.     int n, m;
    24.     scanf("%d%d", &n, &m);
    25.     fill(d[0], d[0] + MAXN * MAXN, INF);
    26.     for (int i = 0; i < n; i++) {
    27.         d[i][i] = 0;
    28.     }
    29.     int u, v, w;
    30.     for (int i = 0; i < m; i++) {
    31.         scanf("%d%d%d", &u, &v, &w);
    32.         d[u][v] = d[v][u] = w;
    33.     }
    34.     floyd(n);
    35.     for (int i = 0; i < n; i++) {
    36.         for (int j = 0; j < n; j++) {
    37.             if (d[i][j] == INF) {
    38.                 printf("-1");
    39.             } else {
    40.                 printf("%d", d[i][j]);
    41.             }
    42.             if (j < n - 1) {
    43.                 printf(" ");
    44.             }
    45.         }
    46.         printf("\n");
    47.     }
    48.     return 0;
    49. }

    10.5最小生成树

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 500;
    8. const int INF = 1e9;
    9.  
    10. struct Edge {
    11.     int v, dis;
    12.     Edge(int _v, int _dis) {
    13.         v = _v, dis = _dis;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int d[MAXN];
    19. bool vis[MAXN];
    20.  
    21. int prim(int n) {
    22.     fill(d, d + MAXN, INF);
    23.     memset(vis, false, sizeof(vis));
    24.     d[0] = 0;
    25.     int weightSum = 0;
    26.     for (int i = 0; i < n; i++) {
    27.         int u = -1, minDis = INF;
    28.         for (int j = 0; j < n; j++) {
    29.             if (!vis[j] && d[j] < minDis) {
    30.                 u = j;
    31.                 minDis = d[j];
    32.             }
    33.         }
    34.         if (u == -1) {
    35.             return -1;
    36.         }
    37.         vis[u] = true;
    38.         weightSum += d[u];
    39.         for (int j = 0; j < G[u].size(); j++) {
    40.             int v = G[u][j].v;
    41.             int dis = G[u][j].dis;
    42.             if (!vis[v] && dis < d[v]) {
    43.                 d[v] = dis;
    44.             }
    45.         }
    46.     }
    47.     return weightSum;
    48. }
    49.  
    50. int main() {
    51.     int n, m;
    52.     scanf("%d%d", &n, &m);
    53.     int u, v, w;
    54.     for (int i = 0; i < m; i++) {
    55.         scanf("%d%d%d", &u, &v, &w);
    56.         G[u].push_back(Edge(v, w));
    57.         G[v].push_back(Edge(u, w));
    58.     }
    59.     int weightSum = prim(n);
    60.     printf("%d", weightSum);
    61.     return 0;
    62. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 10000;
    8.  
    9. struct Edge {
    10.     int u, v, w;
    11.     Edge(int _u, int _v, int _w) {
    12.         u = _u, v = _v, w = _w;
    13.     }
    14. };
    15.  
    16. vector edges;
    17.  
    18. bool cmp(Edge a, Edge b) {
    19.     return a.w < b.w;
    20. }
    21.  
    22. int father[MAXN];
    23.  
    24. int findFather(int x) {
    25.     int xCopy = x;
    26.     while (father[x] != x) {
    27.         x = father[x];
    28.     }
    29.     int root = x;
    30.     x = xCopy;
    31.     while (father[x] != x) {
    32.         int fatherX = father[x];
    33.         father[x] = root;
    34.         x = fatherX;
    35.     }
    36.     return root;
    37. }
    38.  
    39. int kruskal(int n, int m) {
    40.     for (int i = 0; i < n; i++) {
    41.         father[i] = i;
    42.     }
    43.     int weightSum = 0, edgeCount = 0;
    44.     sort(edges.begin(), edges.end(), cmp);
    45.     for (int i = 0; i < m; i++) {
    46.         int faU = findFather(edges[i].u);
    47.         int faV = findFather(edges[i].v);
    48.         if (faU != faV) {
    49.             father[faU] = faV;
    50.             weightSum += edges[i].w;
    51.             edgeCount++;
    52.         }
    53.         if (edgeCount == n - 1) {
    54.             break;
    55.         }
    56.     }
    57.     if (edgeCount != n - 1) {
    58.         return -1;
    59.     } else {
    60.         return weightSum;
    61.     }
    62. }
    63.  
    64. int main() {
    65.     int n, m;
    66.     scanf("%d%d", &n, &m);
    67.     int u, v, w;
    68.     for (int i = 0; i < m; i++) {
    69.         scanf("%d%d%d", &u, &v, &w);
    70.         edges.push_back(Edge(u, v, w));
    71.     }
    72.     int weightSum = kruskal(n, m);
    73.     printf("%d", weightSum);
    74.     return 0;
    75. }

    10.6拓扑排序

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8.  
    9. vector<int> G[MAXN];
    10. int inDegree[MAXN];
    11. vector<int> topoOrder;
    12.  
    13. void topoSort(int n) {
    14.     priority_queue<int, vector<int>, greater<int> > q;
    15.     for (int i = 0; i < n; i++) {
    16.         if (inDegree[i] == 0) {
    17.             q.push(i);
    18.         }
    19.     }
    20.     while (!q.empty()) {
    21.         int u = q.top();
    22.         q.pop();
    23.         topoOrder.push_back(u);
    24.         for (int i = 0; i < G[u].size(); i++) {
    25.             int v = G[u][i];
    26.             inDegree[v]--;
    27.             if (inDegree[v] == 0) {
    28.                 q.push(v);
    29.             }
    30.         }
    31.         G[u].clear();
    32.     }
    33. }
    34.  
    35. int main() {
    36.     int n, m;
    37.     scanf("%d%d", &n, &m);
    38.     int u, v;
    39.     for (int i = 0; i < m; i++) {
    40.         scanf("%d%d", &u, &v);
    41.         G[u].push_back(v);
    42.         inDegree[v]++;
    43.     }
    44.     topoSort(n);
    45.     for (int i = 0; i < topoOrder.size(); i++) {
    46.         printf("%d", topoOrder[i]);
    47.         if (i < (int)topoOrder.size() - 1) {
    48.             printf(" ");
    49.         }
    50.     }
    51.     return 0;
    52. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8.  
    9. vector<int> G[MAXN];
    10. int inDegree[MAXN];
    11.  
    12. bool topoSort(int n) {
    13.     int vertexCount = 0;
    14.     priority_queue<int, vector<int>, greater<int> > q;
    15.     for (int i = 0; i < n; i++) {
    16.         if (inDegree[i] == 0) {
    17.             q.push(i);
    18.         }
    19.     }
    20.     while (!q.empty()) {
    21.         int u = q.top();
    22.         q.pop();
    23.         for (int i = 0; i < G[u].size(); i++) {
    24.             int v = G[u][i];
    25.             inDegree[v]--;
    26.             if (inDegree[v] == 0) {
    27.                 q.push(v);
    28.             }
    29.         }
    30.         G[u].clear();
    31.         vertexCount++;
    32.     }
    33.     return vertexCount == n;
    34. }
    35.  
    36. int main() {
    37.     int n, m;
    38.     scanf("%d%d", &n, &m);
    39.     int u, v;
    40.     for (int i = 0; i < m; i++) {
    41.         scanf("%d%d", &u, &v);
    42.         G[u].push_back(v);
    43.         inDegree[v]++;
    44.     }
    45.     printf(topoSort(n) ? "Yes" : "No");
    46.     return 0;
    47. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. const int MAXN = 100;
    8.  
    9. vector<int> G[MAXN];
    10. int inDegree[MAXN];
    11. vector<int> topoOrder;
    12.  
    13. int topoSort(int n) {
    14.     int vertexCount = 0;
    15.     priority_queue<int, vector<int>, greater<int> > q;
    16.     for (int i = 0; i < n; i++) {
    17.         if (inDegree[i] == 0) {
    18.             q.push(i);
    19.         }
    20.     }
    21.     while (!q.empty()) {
    22.         int u = q.top();
    23.         q.pop();
    24.         topoOrder.push_back(u);
    25.         for (int i = 0; i < G[u].size(); i++) {
    26.             int v = G[u][i];
    27.             inDegree[v]--;
    28.             if (inDegree[v] == 0) {
    29.                 q.push(v);
    30.             }
    31.         }
    32.         G[u].clear();
    33.         vertexCount++;
    34.     }
    35.     return vertexCount;
    36. }
    37.  
    38. int main() {
    39.     int n, m;
    40.     scanf("%d%d", &n, &m);
    41.     int u, v;
    42.     for (int i = 0; i < m; i++) {
    43.         scanf("%d%d", &u, &v);
    44.         G[u].push_back(v);
    45.         inDegree[v]++;
    46.     }
    47.     int learnCount = topoSort(n);
    48.     if (learnCount == n) {
    49.         printf("Yes\n");
    50.         for (int i = 0; i < topoOrder.size(); i++) {
    51.             printf("%d", topoOrder[i]);
    52.             if (i < (int)topoOrder.size() - 1) {
    53.                 printf(" ");
    54.             }
    55.         }
    56.     } else {
    57.         printf("No\n%d\n", n - learnCount);
    58.     }
    59.     return 0;
    60. }

    10.7关键路径

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7.  
    8. const int MAXN = 100;
    9.  
    10. struct Edge {
    11.     int v, w;
    12.     Edge(int _v, int _w) {
    13.         v = _v, w = _w;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int inDegree[MAXN] = {0};
    19. vector<int> topoOrder;
    20. int ve[MAXN], vl[MAXN];
    21. vector<int> activity[MAXN];
    22.  
    23. bool topoSort(int n) {
    24.     priority_queue<int, vector<int>, greater<int> > q;
    25.     for (int i = 0; i < n; i++) {
    26.         if (inDegree[i] == 0) {
    27.             q.push(i);
    28.         }
    29.     }
    30.     while (!q.empty()) {
    31.         int u = q.top();
    32.         q.pop();
    33.         topoOrder.push_back(u);
    34.         for (int i = 0; i < G[u].size(); i++) {
    35.             int v = G[u][i].v;
    36.             inDegree[v]--;
    37.             if (inDegree[v] == 0) {
    38.                 q.push(v);
    39.             }
    40.             if (ve[u] + G[u][i].w > ve[v]) {
    41.                 ve[v] = ve[u] + G[u][i].w;
    42.             }
    43.         }
    44.     }
    45.     return (int)topoOrder.size() == n;
    46. }
    47.  
    48. int getCriticalPathLength(int n) {
    49.     memset(ve, 0, sizeof(ve));
    50.     if (!topoSort(n)) {
    51.         return -1;
    52.     }
    53.     int maxLength = 0;
    54.     for(int i = 0; i < n; i++) {
    55.         if(ve[i] > maxLength) {
    56.             maxLength = ve[i];
    57.         }
    58.     }
    59.     return maxLength;
    60. }
    61.  
    62. int main() {
    63.     int n, m;
    64.     scanf("%d%d", &n, &m);
    65.     int u, v, w;
    66.     for (int i = 0; i < m; i++) {
    67.         scanf("%d%d%d", &u, &v, &w);
    68.         G[u].push_back(Edge(v, w));
    69.         inDegree[v]++;
    70.     }
    71.     int pathLength = getCriticalPathLength(n);
    72.     if (pathLength == -1) {
    73.         printf("No");
    74.     } else {
    75.         printf("Yes\n%d", pathLength);
    76.     }
    77.     return 0;
    78. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7.  
    8. const int MAXN = 100;
    9.  
    10. struct Edge {
    11.     int v, w;
    12.     Edge(int _v, int _w) {
    13.         v = _v, w = _w;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int inDegree[MAXN] = {0};
    19. vector<int> topoOrder;
    20. int ve[MAXN], vl[MAXN];
    21. vector<int> activity[MAXN];
    22.  
    23. bool topoSort(int n) {
    24.     priority_queue<int, vector<int>, greater<int> > q;
    25.     for (int i = 0; i < n; i++) {
    26.         if (inDegree[i] == 0) {
    27.             q.push(i);
    28.         }
    29.     }
    30.     while (!q.empty()) {
    31.         int u = q.top();
    32.         q.pop();
    33.         topoOrder.push_back(u);
    34.         for (int i = 0; i < G[u].size(); i++) {
    35.             int v = G[u][i].v;
    36.             inDegree[v]--;
    37.             if (inDegree[v] == 0) {
    38.                 q.push(v);
    39.             }
    40.             if (ve[u] + G[u][i].w > ve[v]) {
    41.                 ve[v] = ve[u] + G[u][i].w;
    42.             }
    43.         }
    44.     }
    45.     return (int)topoOrder.size() == n;
    46. }
    47.  
    48. int getCriticalPath(int n) {
    49.     memset(ve, 0, sizeof(ve));
    50.     if (!topoSort(n)) {
    51.         return -1;
    52.     }
    53.     int maxLength = 0;
    54.     for(int i = 0; i < n; i++) {
    55.         if(ve[i] > maxLength) {
    56.             maxLength = ve[i];
    57.         }
    58.     }
    59.     fill(vl, vl + n, maxLength);
    60.  
    61.     for (int i = (int)topoOrder.size() - 1; i >= 0; i--) {
    62.         int u = topoOrder[i];
    63.         for (int j = 0; j < G[u].size(); j++) {
    64.             int v = G[u][j].v;
    65.             int w = G[u][j].w;
    66.             if (vl[v] - w < vl[u]) {
    67.                 vl[u] = vl[v] - w;
    68.             }
    69.         }
    70.     }
    71.  
    72.     for (int u = 0; u < n; u++) {
    73.         for (int i = 0; i < G[u].size(); i++) {
    74.             int v = G[u][i].v;
    75.             int w = G[u][i].w;
    76.             int e = ve[u], l = vl[v] - w;
    77.             if (e == l) {
    78.                 activity[u].push_back(v);
    79.             }
    80.         }
    81.     }
    82.     return maxLength;
    83. }
    84.  
    85. int main() {
    86.     int n, m;
    87.     scanf("%d%d", &n, &m);
    88.     int u, v, w;
    89.     for (int i = 0; i < m; i++) {
    90.         scanf("%d%d%d", &u, &v, &w);
    91.         G[u].push_back(Edge(v, w));
    92.         inDegree[v]++;
    93.     }
    94.     if (getCriticalPath(n) == -1) {
    95.         printf("No");
    96.     } else {
    97.         printf("Yes\n");
    98.         for (int i = 0; i < n; i++) {
    99.             sort(activity[i].begin(), activity[i].end());
    100.             for (int j = 0; j < activity[i].size(); j++) {
    101.                 printf("%d %d\n", i, activity[i][j]);
    102.             }
    103.         }
    104.     }
    105.     return 0;
    106. }

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7.  
    8. const int MAXN = 100;
    9.  
    10. struct Edge {
    11.     int v, w;
    12.     Edge(int _v, int _w) {
    13.         v = _v, w = _w;
    14.     }
    15. };
    16.  
    17. vector G[MAXN];
    18. int inDegree[MAXN] = {0}, inDegreeOrigin[MAXN] = {0};
    19. vector<int> topoOrder;
    20. int ve[MAXN], vl[MAXN];
    21. vector<int> activity[MAXN];
    22.  
    23. bool topoSort(int n) {
    24.     priority_queue<int, vector<int>, greater<int> > q;
    25.     for (int i = 0; i < n; i++) {
    26.         if (inDegree[i] == 0) {
    27.             q.push(i);
    28.         }
    29.     }
    30.     while (!q.empty()) {
    31.         int u = q.top();
    32.         q.pop();
    33.         topoOrder.push_back(u);
    34.         for (int i = 0; i < G[u].size(); i++) {
    35.             int v = G[u][i].v;
    36.             inDegree[v]--;
    37.             if (inDegree[v] == 0) {
    38.                 q.push(v);
    39.             }
    40.             if (ve[u] + G[u][i].w > ve[v]) {
    41.                 ve[v] = ve[u] + G[u][i].w;
    42.             }
    43.         }
    44.     }
    45.     return (int)topoOrder.size() == n;
    46. }
    47.  
    48. int getCriticalPath(int n) {
    49.     memset(ve, 0, sizeof(ve));
    50.     if (!topoSort(n)) {
    51.         return -1;
    52.     }
    53.     int maxLength = 0;
    54.     for(int i = 0; i < n; i++) {
    55.         if(ve[i] > maxLength) {
    56.             maxLength = ve[i];
    57.         }
    58.     }
    59.     fill(vl, vl + n, maxLength);
    60.  
    61.     for (int i = (int)topoOrder.size() - 1; i >= 0; i--) {
    62.         int u = topoOrder[i];
    63.         for (int j = 0; j < G[u].size(); j++) {
    64.             int v = G[u][j].v;
    65.             int w = G[u][j].w;
    66.             if (vl[v] - w < vl[u]) {
    67.                 vl[u] = vl[v] - w;
    68.             }
    69.         }
    70.     }
    71.  
    72.     for (int u = 0; u < n; u++) {
    73.         for (int i = 0; i < G[u].size(); i++) {
    74.             int v = G[u][i].v;
    75.             int w = G[u][i].w;
    76.             int e = ve[u], l = vl[v] - w;
    77.             if (e == l) {
    78.                 activity[u].push_back(v);
    79.             }
    80.         }
    81.     }
    82.     return maxLength;
    83. }
    84.  
    85. vector<int> criticalPath;
    86. void printCriticalPath(int u) {
    87.     if(activity[u].size() == 0) {
    88.         criticalPath.push_back(u);
    89.         for(int i = 0; i < criticalPath.size(); i++) {
    90.             printf("%d", criticalPath[i]);
    91.             if(i < criticalPath.size() - 1) {
    92.                 printf("->");
    93.             } else {
    94.                 printf("\n");
    95.             }
    96.         }
    97.         criticalPath.pop_back();
    98.         return;
    99.     }
    100.     criticalPath.push_back(u);
    101.     sort(activity[u].begin(), activity[u].end());
    102.     for(int i = 0; i < activity[u].size(); i++) {
    103.         printCriticalPath(activity[u][i]);
    104.     }
    105.     criticalPath.pop_back();
    106. }
    107.  
    108. int main() {
    109.     int n, m;
    110.     scanf("%d%d", &n, &m);
    111.     int u, v, w;
    112.     for (int i = 0; i < m; i++) {
    113.         scanf("%d%d%d", &u, &v, &w);
    114.         G[u].push_back(Edge(v, w));
    115.         inDegree[v]++;
    116.         inDegreeOrigin[v]++;
    117.     }
    118.     if (getCriticalPath(n) == -1) {
    119.         printf("No");
    120.     } else {
    121.         printf("Yes\n");
    122.         for(int i = 0; i < n; i++) {
    123.             if(inDegreeOrigin[i] == 0 && activity[i].size() != 0) {
    124.                 printCriticalPath(i);
    125.             }
    126.         }
    127.     }
    128.     return 0;
    129. }

  • 相关阅读:
    GPO：部署 ADMX/ADML Template
    debian/ubuntu/windows配置wiregurad内网服务器（包含掉线自启动）
    Numpy数组计算实训
    基于 HBase & Phoenix 构建实时数仓（2）—— HBase 完全分布式安装
    _tkinter.TclError: no display name and no $DISPLAY environment variable 解决
    Python —— OS module
    攻防世界WEB练习区（backup、cookie、disabled_button）
    关于http网络通信数据包封装的过程
    Sqlite查询结果为List＜T＞
    LeetCode刷题复盘笔记—一文搞懂纯完全背包问题（动态规划系列第十一篇）
  • 原文地址：https://blog.csdn.net/qq_62704693/article/details/140377633