• SDUT PTA 图论

    7-1 邻接矩阵表示法创建无向图

    采用邻接矩阵表示法创建无向图G ，依次输出各顶点的度。

    输入格式:

    输入第一行中给出2个整数i(0 输入第二行为顶点的信息，每个顶点只能用一个字符表示。
    依次输入j行，每行输入一条边依附的顶点。

    输出格式:

    依次输出各顶点的度，行末没有最后的空格。

    输入样例:

    1. 5 7
    2. ABCDE
    3. AB
    4. AD
    5. BC
    6. BE
    7. CD
    8. CE
    9. DE

    输出样例:

    2 3 3 3 3
    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int i, j;
    7.     cin >> i >> j;
    8.     string s;
    9.     cin >> s;
    10.     map<char , int>mp;
    11.     while(j--){
    12.         char x, y;
    13.         cin >> x >> y;
    14.         mp[x]++;
    15.         mp[y]++;
    16.     }
    17.     for(int k = 0; k < i; k++){
    18.         if(k == 0) cout << mp[s[k]];
    19.         else cout << ' ' << mp[s[k]];
    20.     }
    21.     return 0;
    22. }


    7-2 邻接表创建无向图

    采用邻接表创建无向图G ，依次输出各顶点的度。

    输入格式:

    输入第一行中给出2个整数i(0 输入第二行为顶点的信息，每个顶点只能用一个字符表示。
    依次输入j行，每行输入一条边依附的顶点。

    输出格式:

    依次输出各顶点的度，行末没有最后的空格。

    输入样例:

    1. 5 7
    2. ABCDE
    3. AB
    4. AD
    5. BC
    6. BE
    7. CD
    8. CE
    9. DE

    输出样例:

    2 3 3 3 3
    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int i, j;
    7.     cin >> i >> j;
    8.     string s;
    9.     cin >> s;
    10.     map<char , int>mp;
    11.     while(j--){
    12.         char x, y;
    13.         cin >> x >> y;
    14.         mp[x]++;
    15.         mp[y]++;
    16.     }
    17.     for(int k = 0; k < i; k++){
    18.         if(k == 0) cout << mp[s[k]];
    19.         else cout << ' ' << mp[s[k]];
    20.     }
    21.     return 0;
    22. }

    7-3 图深度优先遍历

    编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

    输入格式:

    输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。

    输出格式:

    输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。

    输入样例1:

    1. 3 3
    2. 0 1
    3. 1 2
    4. 0 2

    输出样例1:

    0 1 2

    输入样例2:

    1. 4 4
    2. 0 2
    3. 0 1
    4. 1 2
    5. 3 0

    输出样例2:

    0 1 2 3 
    1. #include
    2. using namespace std;
    3. // vector存图
    4. const int N = 1e5+10;
    5. vector<int> a[N];
    6. queue<int>q;
    7. int n, e;
    8. bool st[N];
    9. void dfs(int s){
    10.     cout << s << " ";
    11.     st[s] = 1;
    12.     for(int j = 0; j < a[s].size(); j++){
    13.         if(!st[a[s][j]]){
    14.             dfs(a[s][j]);
    15.         }
    16.     }
    17. }
    18. // void bfs(int s){
    19. //     memset(st, 0, sizeof(st));// 一定！一定！！不要忘了清空！！！
    20. //     q.push(s);
    21. //     cout << s << " ";
    22. //     st[s] = 1;
    23. //     while (q.size())
    24. //     {
    25. //         int t = q.front(); q.pop();
    26.         
    27. //         for(int j = 0; j < a[t].size(); j++){
    28. //             int x = a[t][j];
    29. //             if(!st[x]){
    30. //                 cout << x << " ";
    31. //                 st[x] = 1;
    32. //                 q.push(x);
    33. //             }
    34. //         }
    35. //     }
    36.     
    37. // }
    38. int main()
    39. {
    40.     cin >> n >> e;
    41.     int u, v;
    42.     for(int i = 0; i < e; i++){
    43.         cin >> u >> v;
    44.         a[u].push_back(v);
    45.     }
    46.     for(int i = 0; i < n; i ++){
    47.         sort(a[i].begin(), a[i].end());
    48.     }
    49.     for(int i = 0; i < n; i++){// 因为不一定是连通图！
    50.         if(!st[i]){
    51.             dfs(i);
    52.         }
    53.     }
    54.     // cout << endl;
    55.     // bfs(1);
    56.     return 0;
    57. }

    7-4 单源最短路径

    请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。

    输入格式:

    输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

    输出格式:

    输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。

    输入样例:

    1. 4 4
    2. 0 1 1
    3. 0 3 1
    4. 1 3 1
    5. 2 0 1

    输出样例:

    1 1 
    1. #include
    2. using namespace std;
    3.  
    4. const int N = 1e4 + 10, M = 5e5 + 10;
    5. const int INF = 0x3f3f3f3f;
    6. int n, m, s, cnt;
    7. int head[N], dist[N];
    8. bool st[N];
    9. struct node{
    10.     int v, w, nxt;
    11. }e[M];
    12. // 链式前向星存图T_T
    13. void add(int u, int v, int w){
    14.     e[cnt].w = w; e[cnt].v = v; 
    15.     e[cnt].nxt = head[u];head[u] = cnt++;
    16. }
    17. typedef pair<int, int>pll;
    18. priority_queue, greater > q;
    19. void dijstra(){
    20.     memset(dist, 0x3f, sizeof(dist));
    21.     dist[s] = 0;
    22.     q.push({0, s});
    23.     while(q.size()){
    24.         pll tmp = q.top();q.pop();
    25.         int d = tmp.first, v = tmp.second;
    26.         if(st[v]) continue;
    27.         st[v] = 1;
    28.         for (int i = head[v]; i != -1; i = e[i].nxt){
    29.             int j = e[i].v;
    30.             if(dist[j] > d + e[i].w){
    31.                 dist[j] = d + e[i].w;
    32.                 q.push({dist[j], j});
    33.             }
    34.         }
    35.     }
    36. }
    37.  
    38.  
    39. int main()
    40. {
    41.     memset(head, -1, sizeof(head));
    42.     cin >> n >> m;
    43.     s = 0;
    44.     int u, v, w;
    45.     for (int i = 0; i < m; i++){
    46.         cin >> u >> v >> w;
    47.         add(u, v, w);
    48.     }
    49.     dijstra();
    50.     for(int i = 1; i < n; i++){
    51.         if(dist[i] == INF) continue;
    52.         else cout << dist[i] << " ";
    53.     }
    54.     return 0;
    55. }

    7-5 列出连通集

    给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

    输入格式:

    输入第1行给出2个整数N(0

    输出格式:

    按照"{ v1​ v2​ ... vk​ }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

    输入样例:

    1. 8 6
    2. 0 7
    3. 0 1
    4. 2 0
    5. 4 1
    6. 2 4
    7. 3 5

    输出样例:

    1. { 0 1 4 2 7 }
    2. { 3 5 }
    3. { 6 }
    4. { 0 1 2 7 4 }
    5. { 3 5 }
    6. { 6 }

    1. #include
    2. using namespace std;
    3. // vector存图
    4. const int N = 1e5+10;
    5. vector<int> a[N];
    6. queue<int>q;
    7. int n, e;
    8. bool st[N];
    9. void dfs(int s){
    10.     cout << " " << s;
    11.     st[s] = 1;
    12.     for(int j = 0; j < a[s].size(); j++){
    13.         if(!st[a[s][j]]){
    14.             dfs(a[s][j]);
    15.         }
    16.     }
    17. }
    18. void bfs(int s){
    19.     q.push(s);
    20.     cout << " " << s;
    21.     st[s] = 1;
    22.     while (q.size())
    23.     {
    24.         int t = q.front(); q.pop();
    25.         for(int j = 0; j < a[t].size(); j++){
    26.             int x = a[t][j];
    27.             if(!st[x]){
    28.                 cout << " " << x;
    29.                 st[x] = 1;
    30.                 q.push(x);
    31.             }
    32.         }
    33.     }
    34. }
    35. int main()
    36. {
    37.     cin >> n >> e;
    38.     int u, v;
    39.     for(int i = 0; i < e; i++){
    40.         cin >> u >> v;
    41.         a[u].push_back(v);
    42. 		a[v].push_back(u);// 无向图
    43.     }
    44.     for(int i = 0; i < n; i ++){
    45.         sort(a[i].begin(), a[i].end());
    46.     }
    47. 	memset(st, 0, sizeof(st));// 一定！一定！！不要忘了清空！！！
    48.     for(int i = 0; i < n; i++){// 因为不一定是连通图！
    49.         if(!st[i]){
    50. 			printf("{");
    51.             dfs(i);
    52. 			printf(" }\n");
    53.         }
    54.     }
    55. 	memset(st, 0, sizeof(st));// 一定！一定！！不要忘了清空！！！
    56. 	for(int i = 0; i < n; i++){// 因为不一定是连通图！
    57.         if(!st[i]){
    58. 			printf("{");
    59.             bfs(i);
    60. 			printf(" }\n");
    61.         }
    62.     }
    63.     // cout << endl;
    64.     // bfs(1);
    65.     return 0;
    66. }

    7-6 哈利·波特的考试

    1. #include
    2. using namespace std;
    3. // Floyd算法--任意两点之间的最短距离
    4. const int N = 302, M = 5e5 + 3;
    5. const int INF = 0x3f3f3f3f;
    6. int mp[N][N];
    7. int n, m;
    8. void Floyed(){
    9.     for(int k = 1; k <= n; k++){
    10.         for(int i = 1; i <= n; i++){
    11.             for(int j = 1; j <= n; j++){
    12.                 mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    13.             }
    14.         }
    15.     }
    16. }
    17. int main(){
    18.     cin >> n >> m;
    19.     // for(int i = 1; i <= n; i++){
    20.     //     for(int j = 1; j <= n; j++){
    21.     //         if(i == j) mp[i][j] = 0;
    22.     //         else mp[i][j] = INF;
    23.     //     }
    24.     // }
    25.     memset(mp, INF, sizeof(mp));
    26.     for(int i = 1; i <= n; i++) mp[i][i] = 0;
    27.     for(int i = 1; i <= m; i++){
    28.         int u, v, w;
    29.         cin >> u >> v >> w;
    30.         mp[u][v] = mp[v][u] = w;
    31.     }
    32.     Floyed();
    33.     int minn = INF, id = 0;
    34.     for(int i = 1; i <= n; i++){// 开始的一个
    35.         int maxn = 0;
    36.         for(int j = 1; j <= n; j++){// 另一个
    37.             maxn = max(maxn, mp[i][j]);
    38.         }// 找到最难变的动物
    39.         if(maxn < minn){
    40.             minn = maxn;
    41.             id = i;
    42.         }// 比较每一个最难变的动物的咒语长度
    43.     }
    44.     if(id) cout << id << " " << minn << endl;
    45.     else cout << "0" << endl;
    46.     return 0;
    47. }

    7-9 哥尼斯堡的“七桥问题”

    哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥

    可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。

    这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？

    输入格式:

    输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。

    输出格式:

    若欧拉回路存在则输出1，否则输出0。

    输入样例1:

    1. 6 10
    2. 1 2
    3. 2 3
    4. 3 1
    5. 4 5
    6. 5 6
    7. 6 4
    8. 1 4
    9. 1 6
    10. 3 4
    11. 3 6

    输出样例1:

    1

    输入样例2:

    1. 5 8
    2. 1 2
    3. 1 3
    4. 2 3
    5. 2 4
    6. 2 5
    7. 5 3
    8. 5 4
    9. 3 4

    输出样例2:

    0
    1. #include
    2. using namespace std;
    3. // dfs判断是否连通，度数是否为偶数判断是否能回到原点
    4. const int N = 1003;
    5. int mp[N][N];
    6. bool vis[N];
    7. int degree[N*2];
    8. int cnt;
    9. int n, m;
    10. void dfs(int s){
    11.     vis[s] = 1;
    12.     cnt++;
    13.     for(int j = 1; j <= n; j++){
    14.         if(mp[s][j] && !vis[j]){
    15.             dfs(j);
    16.         }
    17.     }
    18. }
    19. int main()
    20. {
    21.     cin >> n >> m;
    22.     for(int i = 1; i <= m; i++){
    23.         int u, v;
    24.         cin >> u >> v;
    25.         mp[u][v] = mp[v][u] = 1;
    26.         degree[u]++; degree[v]++;
    27.     }
    28.     bool f = 1;
    29.     for(int i = 1; i <= n; i++){
    30.         if(degree[i] % 2 != 0){
    31.             f = 0;
    32.         }
    33.     }
    34.     dfs(1);
    35.     if(!f) cout << "0" << endl;
    36.     else{
    37.         if(cnt == n) cout << "1" << endl;
    38.         else cout << "0" << endl;
    39.     }
    40.     return 0;
    41. }

    7-10 公路村村通

    现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

    输入格式:

    输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

    输出格式:

    输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

    输入样例:

    1. 6 15
    2. 1 2 5
    3. 1 3 3
    4. 1 4 7
    5. 1 5 4
    6. 1 6 2
    7. 2 3 4
    8. 2 4 6
    9. 2 5 2
    10. 2 6 6
    11. 3 4 6
    12. 3 5 1
    13. 3 6 1
    14. 4 5 10
    15. 4 6 8
    16. 5 6 3

    输出样例:

    12
    1. #include
    2. using namespace std;
    3.  
    4. const int N = 1003;
    5. const int INF = 0x3f3f3f3f;
    6. int mp[N][N];
    7. bool vis[N];
    8. int dis[N];
    9. int n, m;
    10. int cnt;
    11. int prime()
    12. {
    13.     memset(dis, INF, sizeof(dis));
    14.     dis[1] = 0;
    15.     int ans = 0;
    16.     for(int i = 1; i <= n; i++){
    17.         int t = 0;
    18.         for(int j = 1; j <= n; j++){
    19.             if(!vis[j] && dis[t] > dis[j]) t = j;
    20.         }
    21.         vis[t] = 1;
    22.         ans += dis[t];
    23.         for(int j = 1; j <= n; j++){
    24.             if(!vis[j]) dis[j] = min(dis[j], mp[t][j]);
    25.         }
    26.     }
    27.     int flag=0;
    28.     for(int i=1; i<=n; i++){
    29.         if(vis[i]!=1){
    30.             flag=1;
    31.             break;
    32.         }
    33.     }// 记录遍历过的点数也不好使，就这种可以。。。
    34.     if(flag == 1) return -1;
    35.     else return ans;
    36. }
    37. int main()
    38. {
    39.     cin >> n >> m;
    40.     memset(mp, INF, sizeof(mp));
    41.     for(int i = 1; i <= m; i++){
    42.         int u, v, w;
    43.         cin >> u >> v >> w;
    44.         mp[u][v] = mp[v][u] = min(mp[u][v], w);
    45.     }
    46.     cout << prime() << endl;
    47.     return 0;
    48. }

    7-11 旅游规划 

    有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

    输入格式:

    输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

    输出格式:

    在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

    输入样例:

    1. 4 5 0 3
    2. 0 1 1 20
    3. 1 3 2 30
    4. 0 3 4 10
    5. 0 2 2 20
    6. 2 3 1 20

    输出样例:

    3 40
    1. #include
    2. using namespace std;
    3.  
    4. const int N = 550;
    5. const int INF = 0x3f3f3f3f;
    6. int mp1[N][N], mp2[N][N];
    7. int n, m, s, d;
    8. bool vis[N];
    9. int dis[N], cost[N];
    10. void dijkstra()
    11. {
    12.     memset(dis, INF, sizeof(dis));
    13.     dis[s] = 0;
    14.     for(int i = 0; i < n; i++){
    15.         int k = -1;
    16.         for(int j = 0; j < n; j++){
    17.             if(!vis[j] && (k == -1 || dis[j] < dis[k])){
    18.                 k = j;
    19.             }
    20.         }
    21.         vis[k] = 1;
    22.         for(int j = 0; j < n; j++){
    23.             if(!vis[j] && dis[k] + mp1[k][j] < dis[j]){
    24.                 dis[j] = dis[k] + mp1[k][j];
    25.                 cost[j] = cost[k] + mp2[k][j];
    26.             }
    27.             else if(!vis[j] && dis[j] == dis[k] + mp1[k][j] && cost[k] + mp2[k][j] < cost[j]){
    28.                 cost[j] = cost[k] + mp2[k][j];
    29.             }
    30.         }
    31.     }
    32. }
    33. int main()
    34. {
    35.     cin >> n >> m >> s >> d;
    36.     memset(mp1, INF, sizeof(mp1));
    37.     memset(mp2, INF, sizeof(mp2));
    38.     for(int i = 0; i < m; i++){
    39.         int u, v, l, w;
    40.         cin >> u >> v >> l >> w;
    41.         mp1[u][v] = mp1[v][u] = l;
    42.         mp2[u][v] = mp2[v][u] = w;
    43.     }
    44.     dijkstra();
    45.     cout << dis[d] << " " << cost[d];
    46.     return 0;
    47. }

     

    7-13 任务调度的合理性 

    假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

    比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

    但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

    输入格式:

    输入说明：输入第一行给出子任务数N（≤100），子任务按1~N编号。随后N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K，随后给出K个子任务编号，整数之间都用空格分隔。

    输出格式:

    如果方案可行，则输出1，否则输出0。

    输入样例1:

    1. 12
    2. 0
    3. 0
    4. 2 1 2
    5. 0
    6. 1 4
    7. 1 5
    8. 2 3 6
    9. 1 3
    10. 2 7 8
    11. 1 7
    12. 1 10
    13. 1 7

    输出样例1:

    1

    输入样例2:

    1. 5
    2. 1 4
    3. 2 1 4
    4. 2 2 5
    5. 1 3
    6. 0

    输出样例2:

    0
    1. #include
    2. using namespace std;
    3. // vector存图、拓扑排序
    4. const int INF = 0x3f3f3f3f;
    5. const int N = 105;
    6. int mp[N][N];
    7. int n, m;
    8. int indegree[N];
    9. int cnt, result;
    10. int ans[N];
    11. vector<int>g[N];
    12. bool topo(){
    13.     int num = 0;
    14.     queue<int>q;
    15.     for(int i = 1; i <= n; i++){
    16.         if(indegree[i] == 0){// 入度为0的点入队
    17.             q.push(i);
    18.         }
    19.     }
    20.     while(!q.empty()){
    21.         int u = q.front(); q.pop();
    22.         for(int i = 0; i < g[u].size(); i++){
    23.             int v = g[u][i];// u的后继结点v
    24.             indegree[v]--;
    25.             if(indegree[v] == 0){// 入度为0的点入队
    26.                 q.push(v);
    27.             }
    28.         }
    29.         g[u].clear();// u的出度全都用过了，所以要清空u的所有出边
    30.         num++;
    31.     }
    32.     if(num == n) return 1;
    33.     else return 0;
    34. }
    35. int main()
    36. {
    37.     cin >> n;
    38.     for(int i = 1; i <= n; i++){
    39.         int x, y;
    40.         cin >> x; 
    41.         indegree[i] = x;
    42.         for(int j = 0; j < x; j++){
    43.             cin >> y;
    44.             g[y].push_back(i);
    45.         }
    46.     }
    47.     if(topo()) cout << "1" << endl;
    48.     else cout << "0" << endl;
    49.     return 0;
    50. }

     

    7-14 最短工期

    一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

    输入格式：

    首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

    输出格式：

    如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

    输入样例 1：

    1. 9 12
    2. 0 1 6
    3. 0 2 4
    4. 0 3 5
    5. 1 4 1
    6. 2 4 1
    7. 3 5 2
    8. 5 4 0
    9. 4 6 9
    10. 4 7 7
    11. 5 7 4
    12. 6 8 2
    13. 7 8 4

    输出样例 1：

    18

    输入样例 2：

    1. 4 5
    2. 0 1 1
    3. 0 2 2
    4. 2 1 3
    5. 1 3 4
    6. 3 2 5

    输出样例 2：

    Impossible
    1. #include
    2. using namespace std;
    3.  
    4. const int INF = 0x3f3f3f3f;
    5. const int N = 105;
    6. int mp[N][N];
    7. int n, m;
    8. int indegree[N];
    9. int cnt, result;
    10. int ans[N];
    11. void topo(){
    12.     while(true){// 为了应和下面的break叭……
    13.         bool f = 0;
    14.         for(int i = 0; i < n; i++){
    15.             if(indegree[i] == 0){// 如果入度为0，即为第一个点
    16.                 for(int j = 0; j < n; j++){// 寻找下一个点
    17.                     if(mp[i][j] != -1){// 如果i可以到j
    18.                         ans[j] = max(ans[j], ans[i] + mp[i][j]);
    19.                         // 对于第j个里程碑，完成全部前序里程碑所用的最短时间
    20.                         result = max(ans[j], result);
    21.                         indegree[j]--;
    22.                     }
    23.                 }
    24.                 indegree[i] = -1;
    25.                 f = 1;
    26.                 cnt++;
    27.             }
    28.         }
    29.         if(f == 0) break;
    30.     }
    31.     if(cnt < n) cout << "Impossible";
    32.     else cout << result;
    33. }
    34. int main()
    35. {
    36.     cin >> n >> m;
    37.     memset(mp, -1, sizeof(mp));
    38.     for(int i = 0; i < m; i++){
    39.         int u, v, w;
    40.         cin >> u >> v >> w;
    41.         mp[u][v] = w;
    42.         indegree[v]++;
    43.     }
    44.     topo();
    45.     return 0;
    46. }

     **还是想不明白为什么用max？？

    7-15 最短路径

    给定一个有N个顶点和E条边的无向图，顶点从0到N−1编号。请判断给定的两个顶点之间是否有路径存在。如果存在，给出最短路径长度。
    这里定义顶点到自身的最短路径长度为0。
    进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

    输入格式:

    输入第1行给出2个整数N(0 随后E行，每行给出一条边的两个顶点。每行中的数字之间用1空格分隔。
    最后一行给出两个顶点编号i，j（0≤i,j

    输出格式:

    如果i和j之间存在路径，则输出"The length of the shortest path between i and j is X."，X为最短路径长度，
    否则输出"There is no path between i and j."。

    输入样例1:

    1. 7 6
    2. 0 1
    3. 2 3
    4. 1 4
    5. 0 2
    6. 1 3
    7. 5 6
    8. 0 3

    输出样例1:

    The length of the shortest path between 0 and 3 is 2.

    输入样例2:

    1. 7 6
    2. 0 1
    3. 2 3
    4. 1 4
    5. 0 2
    6. 1 3
    7. 5 6
    8. 0 6

    输出样例2:

    There is no path between 0 and 6.
    1. // 数据量很小，可以用邻接矩阵存图
    2. #include
    3. using namespace std;
    4.  
    5. const int INF = 0x3f3f3f3f;
    6. const int N = 14;
    7. int mp[N][N];
    8. int n, m;
    9. void floyed(){
    10.     for(int k = 0; k < n; k++){
    11.         for(int i = 0; i < n; i++){
    12.             for(int j = 0; j < n; j++){
    13.                 mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    14.             }
    15.         }
    16.     }
    17. }
    18. int main()
    19. {
    20.     cin >> n >> m;
    21.     memset(mp, INF, sizeof(mp));
    22.     for(int i = 0; i < n; i++) mp[i][i] = 0;
    23.     for(int i = 0; i < m; i++){
    24.         int u, v;
    25.         cin >> u >> v;
    26.         mp[u][v] = mp[v][u] = min(mp[u][v], 1);
    27.     }
    28.     floyed();
    29.     int s, e;
    30.     cin >> s >> e;
    31.     if(mp[s][e] < INF) 
    32.         printf("The length of the shortest path between %d and %d is %d.", s, e, mp[s][e]);
    33.     else printf("There is no path between %d and %d.", s, e);
    34.     return 0;
    35. }

    7-16 最短路径算法(Floyd-Warshall)

    在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。

    解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。
    而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。

    在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并使用Floyd算法求出每一对顶点间的最短路径长度。

    输入格式:

    输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。

    以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。
    当i和j相等的时候，保证对应的整数为0。

    输出格式:

    共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。

    如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。

    请在每个整数后输出一个空格，并请注意行尾输出换行。

    输入样例:

    1. 4
    2. 0 3 0 1
    3. 0 0 4 0
    4. 2 0 0 0
    5. 0 0 1 0

    输出样例:

    1. 0 3 2 1 
    2. 6 0 4 7 
    3. 2 5 0 3 
    4. 3 6 1 0 
    1. #include
    2. using namespace std;
    3.  
    4. const int INF = 0x3f3f3f3f;
    5. const int N = 55;
    6. int mp[N][N];
    7. int n;
    8. void floyed(){
    9.     for(int k = 0; k < n; k++){
    10.         for(int i = 0; i < n; i++){
    11.             for(int j = 0; j < n; j++){
    12.                 mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    13.             }
    14.         }
    15.     }
    16. }
    17. int main()
    18. {
    19.     cin >> n;
    20.     memset(mp, INF, sizeof(mp));
    21.     for(int i = 0; i < n; i++) mp[i][i] = 0;
    22.     for(int i = 0; i < n; i++){
    23.         for(int j = 0; j < n; j++){
    24.             int x;
    25.             cin >> x;
    26.             if(x != 0) mp[i][j] = x;// 楞个回事哦……
    27.         }// 难道是。。数值为0就直接不算进去了？
    28.     }
    29.     floyed();
    30.     for(int i = 0; i < n; i++){
    31.         for(int j = 0; j < n; j++){
    32.             if(mp[i][j] == INF) cout << "-1" << " ";
    33.             else cout << mp[i][j] << " ";
    34.         }
    35.         cout << endl;
    36.     }
    37.     
    38.     return 0;
    39. }

  • 相关阅读:
    Mysql JDBC 编程
    HDLbits exercises 6 (MULTIPLEXERS节选题)
    java8新特性-lambda表达式 和 方法引用
    Trie字符串统计
    一个.Net开发的轻量级SQLite数据库ORM
    【Mindspore】ResizeArea涉及的infershape问题
    《痞子衡嵌入式半月刊》 第 103 期
    C++ string 类的其他操作
    PostgreSQL使用pgAdmin创建表后查询时提示“关系不存在”
    基于自动化设备和现代化仓储精益管理思想开发的仓库管理系统
  • 原文地址：https://blog.csdn.net/qq_62846665/article/details/127593795