鱼C论坛

 找回密码
 立即注册
查看: 1363|回复: 0

[技术交流] PYA A_1003 Emergency

[复制链接]
发表于 2020-2-20 12:17:17 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 798236606 于 2020-2-22 15:53 编辑

传送门:https://pintia.cn/problem-sets/9 ... /994805523835109376

解:
最短路径

1.迪杰斯特拉
  1. #include <cstdio>
  2. #include <climits>
  3. #include <algorithm>

  4. using namespace std;

  5. const int maxn = 510;

  6. int n, m, c1, c2;
  7. int G[maxn][maxn];
  8. int men[maxn];//存放点权,即救援队数
  9. int num[maxn];//存放到每个点的最短路径数
  10. int w[maxn];//存放可聚集的队伍数
  11. int v[maxn];//存放最短路径长度
  12. bool vis[maxn];//是否访问过

  13. void DJS(int s)
  14. {
  15.     fill(v, v + n, INT_MAX);
  16.     fill(num, num + n, 0);
  17.     fill(w , w + n, 0);
  18.     v[s] = 0;
  19.     w[s] = men[s];
  20.     num[s] = 1;

  21.     for (int i = 0; i < n; i++)
  22.     {   
  23.         int u = -1, min = INT_MAX;

  24.         for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
  25.             if (!vis[i] && v[i] < min)  min = v[u = i];

  26.         if (u == -1) return;//如果剩下的顶点与源点不通,返回

  27.         vis[u] = true;

  28.         for (int j = 0; j < n; j++)
  29.         {
  30.             if (vis[j] || G[u][j] == INT_MAX) continue;

  31.             int t = v[u] + G[u][j];

  32.             if (t < v[j])
  33.             {
  34.                 v[j] = t;
  35.                 num[j] = num[u];
  36.                 w[j] = w[u] + men[j];
  37.             }  
  38.             else if (t == v[j])
  39.             {
  40.                 num[j] += num[u];

  41.                 if (w[u] + men[j] > w[j]) w[j] = w[u] + men[j];
  42.             }
  43.         }
  44.     }
  45. }

  46. int main(void)
  47. {
  48.     scanf("%d %d %d %d", &n, &m, &c1, &c2);

  49.     fill(G[0], G[0] + maxn * maxn, INT_MAX);

  50.     for (int i = 0; i < n; i++)
  51.         scanf("%d", men + i);

  52.     while (m--)
  53.     {
  54.         int a, b, l;

  55.         scanf("%d %d %d", &a, &b, &l);

  56.         G[a][b] = G[b][a] = l;
  57.     }

  58.     DJS(c1);

  59.     printf("%d %d", num[c2], w[c2]);

  60.     return 0;
  61. }
复制代码


2.迪杰斯特拉 + DFS (模板)
  1. #include <cstdio>
  2. #include <climits>
  3. #include <vector>
  4. #include <algorithm>

  5. using namespace std;

  6. const int maxn = 510;

  7. int n, m, c1, c2;
  8. int G[maxn][maxn];
  9. int weight[maxn];//存放点权,即救援队数
  10. int d[maxn];//存放最短路径长度
  11. bool vis[maxn];//是否访问过
  12. vector<int> pre[maxn];//存放顶点在最短路径中的前驱

  13. void DJS(int s)
  14. {
  15.     fill(d, d + n, INT_MAX);
  16.     d[s] = 0;

  17.     for (int i = 0; i < n; i++)
  18.     {   
  19.         int u = -1, min = INT_MAX;

  20.         for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
  21.             if (!vis[i] && d[i] < min)  min = d[u = i];

  22.         if (u == -1) return;//如果剩下的顶点与源点不通,返回

  23.         vis[u] = true;

  24.         for (int v = 0; v < n; v++)
  25.         {
  26.             if (vis[v] || G[u][v] == INT_MAX) continue;

  27.             int t = d[u] + G[u][v];

  28.             if (t < d[v])
  29.             {
  30.                 d[v] = t;
  31.                 pre[v].clear();
  32.                 pre[v].push_back(u);
  33.             }  
  34.             else if (t == d[v])
  35.                 pre[v].push_back(u);
  36.         }
  37.     }
  38. }

  39. int num = 0;//存放最短路径条数
  40. int opt_w = 0;//存放最大点权和
  41. vector<int> path;

  42. void DFS(int v)
  43. {
  44.     if (v == c1)//递归边界,如果遍历到起点
  45.     {
  46.         path.push_back(v);

  47.         num++;

  48.         int val = 0;
  49.         for (int i = path.size() - 1; i >= 0; i--)
  50.             val += weight[path[i]];

  51.         if (val > opt_w) opt_w = val;

  52.         path.pop_back();

  53.         return;
  54.     }

  55.     path.push_back(v);

  56.     for (int i = 0; i < pre[v].size(); i++)
  57.         DFS(pre[v][i]);

  58.     path.pop_back();
  59. }

  60. int main(void)
  61. {
  62.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
  63.    
  64.     fill(G[0], G[0] + maxn * maxn, INT_MAX);

  65.     for (int i = 0; i < n; i++)
  66.         scanf("%d", weight + i);
  67.    
  68.     while (m--)
  69.     {
  70.         int a, b, l;
  71.         scanf("%d %d %d", &a, &b, &l);

  72.         G[a][b] = G[b][a] = l;
  73.     }

  74.     DJS(c1);
  75.     DFS(c2);

  76.     printf("%d %d", num, opt_w);

  77.     return 0;
  78. }
复制代码


3.BF算法
  1. #include <cstdio>
  2. #include <climits>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <algorithm>

  7. using namespace std;

  8. const int maxn = 510;

  9. typedef struct node{
  10.     int id, dis;

  11.     node (int _id, int _dis) : id(_id), dis(_dis) {};
  12. }Node;

  13. int n, m, c1, c2;
  14. int weight[maxn];//存放点权,即救援队数
  15. int num[maxn];//存放到每个点的最短路径数
  16. int w[maxn];//存放可聚集的队伍数
  17. int d[maxn];//存放最短路径长度
  18. vector<Node> adj[maxn];//邻接表
  19. set<int> pre[maxn];//存放顶点在最短路径中的前驱

  20. void BF(int s)
  21. {
  22.     fill(d, d + n, INT_MAX);
  23.     memset(w, 0, sizeof(w));
  24.     memset(num, 0, sizeof(num));

  25.     w[s] = weight[s];
  26.     d[s] = 0;
  27.     num[s] = 1;

  28.     for (int i = 0; i < n - 1; i++)
  29.     {
  30.         for (int u = 0; u < n; u++)
  31.         {
  32.             if (d[u] == INT_MAX) continue;

  33.             for (int v = 0; v < adj[u].size(); v++)
  34.             {
  35.                 int id = adj[u][v].id, dis = adj[u][v].dis;

  36.                 if (dis + d[u] < d[id])
  37.                 {
  38.                     d[id] = dis + d[u];
  39.                     num[id] = num[u];
  40.                     w[id] = weight[id] + w[u];
  41.                     pre[id].clear();
  42.                     pre[id].insert(u);
  43.                 }
  44.                 else if (dis + d[u] == d[id])
  45.                 {
  46.                     if (weight[id] + w[u] > w[id])
  47.                         w[id] = weight[id] + w[u];

  48.                     num[id] = 0;
  49.                     
  50.                     pre[id].insert(u);
  51.                     for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
  52.                         num[id] += num[*it];
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }

  58. int main(void)
  59. {
  60.     // freopen("input.txt", "r", stdin);
  61.     scanf("%d %d %d %d", &n, &m, &c1, &c2);

  62.     for (int i = 0; i < n; i++)
  63.         scanf("%d", weight + i);
  64.    
  65.     while (m--)
  66.     {
  67.         int a, b, l;
  68.         scanf("%d %d %d", &a, &b, &l);

  69.         adj[a].push_back(node(b, l));
  70.         adj[b].push_back(node(a, l));
  71.     }

  72.     BF(c1);

  73.     printf("%d %d", num[c2], w[c2]);

  74.     return 0;
  75. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 15:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表