[toc]

单源最短路的建图方式

1129. 热浪

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！
他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。
农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。
这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用（包括油费，过路费等等）。
给定一个地图，包含 C 条直接连接 2 个城镇的道路。
每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。
求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;
第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。
输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。
数据保证至少存在一条道路。
输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2510;
  9. int n, m;
  10. int ts,td;
  11. int g[N][N];
  12. int dist[N];
  13. bool st[N];
  15. int dijkstra()
  16. {
  17.     memset(dist, 0x3f, sizeof dist);
  18.     dist[ts] = 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[td];
  35. }
  37. int main()
  38. {
  39.     scanf("%d%d", &n, &m);
  40.     scanf("%d%d", &ts, &td);
  41.     memset(g, 0x3f, sizeof g);
  42.     while (m -- )
  43.     {
  44.         int a, b, c;
  45.         scanf("%d%d%d", &a, &b, &c);
  46.         g[a][b] = c; // 双向通道
  47.         g[b][a] = c;
  48.     }
  50.     printf("%d\n", dijkstra());
  52.     return 0;
  53. }

1128. 信使

战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。
指挥部设在第一个哨所。
当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 n 个哨所全部接到命令后，送信才算成功。
因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。
现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。
输入格式
第 1 行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。
第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要花费 k 天。
输出格式
一个整数，表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信，就输出-1。
输入样例：
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例：
11

做一遍dij，然后求最长路径，如果最长路径是一开始设置的正无穷，说明不能到达，否则最长路径就是答案

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2510;
  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.     dist[1] = 0;
  19.     for (int i = 0; i < n - 1; i ++ )  // 这里是n-1次
  20.     {
  21.         int t = -1;
  22.         for (int j = 1; j <= n; j ++ )
  23.             if (!st[j] && (t == -1 || dist[t] > dist[j]))
  24.                 t = j;
  26.         for (int j = 1; j <= n; j ++ )
  27.             dist[j] = min(dist[j], dist[t] + g[t][j]);
  29.         st[t] = true;
  30.     }
  31. }
  33. int main()
  34. {
  35.     scanf("%d%d", &n, &m);
  36.     memset(g, 0x3f, sizeof g);
  37.     while (m -- )
  38.     {
  39.         int a, b, c;
  40.         scanf("%d%d%d", &a, &b, &c);
  41.         g[a][b] = c; // 双向通道
  42.         g[b][a] = c;
  43.     }
  44.     dijkstra();
  45.     int res=0;
  46.     for (int i = 1; i <= n; i ++ ){
  47.         res = max(res,dist[i]);
  48.     }
  49.     if(res==0x3f3f3f3f){
  50.         cout << -1 <<endl;
  51.     }else{
  52.         cout << res;
  53.     }
  55.     return 0;
  56. }

1127. 香甜的黄油

农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。
当然，他将付出额外的费用在奶牛上。
农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。
他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。
给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。
第二行第 N+1 行: 1 到 N 头奶牛所在的牧场号。
第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。
输出格式
共一行，输出奶牛必须行走的最小的距离和。
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8

以每个点为起点，求最短路

  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,INF = 0X3f3f3f3f;
  14. vector<PII>h[N];
  15. int n,m,p;
  16. int dist[N],id[N];
  17. bool st[N];
  19. int spfa(int u){
  20.     memset(dist, 0x3f, sizeof dist);
  21.     dist[u] = 0;
  22.     queue<int>q;
  23.     q.push(u);
  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.     }
  42.     int res=0;
  43.     for (int i = 0; i < n; i ++ ){
  44.         int j = id[i];
  45.         if(dist[j]==INF){ // 说明这头牛到不了，返回正无穷
  46.             return INF;
  47.         }
  48.         res+=dist[j];
  49.     }
  50.     return res;
  51. }
  53. int main()
  54. {
  55.     cin >> n >> p >> m;
  56.     for (int i = 0; i < n; i ++ ){
  57.         cin >> id[i];
  58.     }
  59.     while (m -- ){
  60.         int a,b,c;
  61.         cin >> a >> b >> c;
  62.         h[a].push_back({b,c});
  63.         h[b].push_back({a,c});
  64.     }
  65.     int res=INF;
  66.     for (int i = 1; i <= p; i ++ ){
  67.         res = min(res,spfa(i));
  68.     }
  69.     cout << res;
  70. }

1126. 最小花费(乘积最大值)

在 n 个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。
输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。
以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。
最后一行输入两个正整数 A,B。
数据保证 A 与 B 之间可以直接或间接地转账。
输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。
精确到小数点后 8 位。
输入样例：
3 3
1 2 1
2 3 2
1 3 3
1 3
输出样例：
103.07153164
image.png

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2010;
  9. int n, m;
  10. double g[N][N];
  11. double dist[N];
  12. bool st[N];
  14. double dijkstra(int start,int end)
  15. {
  16.     memset(dist, 0, sizeof dist); // 乘积最大值初始化为0
  17.     dist[start] = 1;   //初始化为1
  19.     for (int i = 0; i < n - 1; i ++ )  // 这里是n-1次
  20.     {
  21.         int t = -1;
  22.         for (int j = 1; j <= n; j ++ )
  23.             if (!st[j] && (t == -1 || dist[j] > dist[t]))
  24.                 t = j;
  26.         for (int j = 1; j <= n; j ++ )
  27.             dist[j] = max(dist[j], dist[t] * g[t][j]);  // 这里求最大
  29.         st[t] = true;
  30.     }
  32.     return dist[end];
  33. }
  35. int main()
  36. {
  37.     scanf("%d%d", &n, &m);
  39.     memset(g, 0, sizeof g);  // 因为是求乘积最大值，所以初始化为0相当于正无穷
  40.     while (m -- )
  41.     {
  42.         int a, b, c;
  43.         scanf("%d%d%d", &a, &b, &c);
  44.         g[a][b] = (100.0-c)/100;
  45.         g[b][a] = (100.0-c)/100;
  46.     }
  47.     int A,B;
  48.     cin >> A >> B;
  49.     double res = 100/dijkstra(A,B);
  50.     printf("%.8lf",res);
  51.     return 0;
  52. }

920. 最优乘车

H 城是一个旅游胜地，每年都有成千上万的人前来观光。
为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。
现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。
写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。
输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。
输入样例：
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2

  1. /*
  2. 将图经一号点的车加入队列
  3.     只要队列不空，取出车来，更新线路上的其他所有点的最短距离
  4.         对于其线路上的每一个点再遍历经过的车，如果没被用过就加入队列中
  5. */
  7. #include <iostream>
  8. #include <cstring>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <queue>
  12. #include <sstream>
  13. #define x first
  14. #define y second
  16. const int N = 510,M=110,INF = 0x3f3f3f3f;
  17. using namespace std;
  18. typedef pair<int, int> PII;
  19. vector<int>line[M]; // i号车的线路
  20. vector<int>pid[N];  // 经过i号点的车有哪些
  21. int cid[N][N];  // i号车j号点对应线路里面的哪个下标
  22. int dist[N];
  23. bool st[N][N];
  24. int m,n;
  26. struct Node{
  27.     int x; // 车
  28.     int y; // 第几次换乘
  29.     int z; // 在这条线路的几号点（这里指下标）换乘
  30. };
  32. void bfs(int start){
  33.     memset(dist, 0x3f, sizeof dist);
  34.     queue<Node>q;
  35.     for(auto c:pid[start]){ // 包含起点的车入队列
  36.         q.push({c,-1,cid[c][start]}); // x表示车，y第几次换乘
  37.         st[c][start] = true;
  38.     }
  39.     while(!q.empty()){
  40.         auto t = q.front(); 
  41.         q.pop();
  42.         int x = t.x; // x表示车，y第几次换乘
  43.         int y = t.y;
  44.         int z = t.z; // 从x车的这条线路上的第几个点开始
  45.         // 用车更新沿线上的点的最短距离
  46.         for (int i = z; i < line[x].size(); i ++ ){
  47.             int point = line[x][i];
  48.             // 看看在这个点能换乘哪些车
  49.             for(auto c:pid[point]){
  50.                 if(!st[c][point]){
  51.                     q.push({c,y+1,cid[c][point]});
  52.                     st[c][point] = true;// 访问过这辆车
  53.                 }
  54.             }
  55.             //cout << point <<" ";
  56.             // 更新线路上点的最短距离
  57.             dist[point] = min(dist[point],y+1);
  58.             if(point==n){ // 已经更新最短了
  59.                 return ;
  60.             }
  61.         }
  62.         //cout << endl;
  63.     }
  64. }
  66. int main()
  67. {
  68.     cin >> m >> n;
  69.     getchar();
  70.     for (int i = 1; i <= m; i ++ ){
  71.         string str;
  72.         getline(cin,str);
  73.         stringstream ssin(str);
  74.         int x;
  75.         int cnt=0;
  76.         while(ssin>>x){
  77.             line[i].push_back(x);
  78.             pid[x].push_back(i);
  79.             cid[i][x] = cnt;
  80.             cnt++;
  81.         }
  82.     }
  83.     bfs(1);
  84.     if(dist[n]==INF){
  85.         puts("NO");
  86.     }else{
  87.         cout << dist[n];
  88.     }
  89. }

image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  6. #include <sstream>
  7. #define x first
  8. #define y second
  10. const int N = 510,M=110,INF = 0x3f3f3f3f;
  11. using namespace std;
  12. int dist[N];
  13. bool g[N][N];
  14. int stop[N];
  15. bool st[N];
  16. int m,n;
  18. void bfs(int start){
  19.     queue<int>q;
  20.     q.push(start);
  21.     st[start] = true;
  22.     memset(dist,0x3f,sizeof dist);
  23.     dist[start] = 0;
  24.     while(!q.empty()){
  25.         auto t = q.front();
  26.         q.pop();
  27.         for (int j = 1; j <= n; j ++ ){
  28.             if(g[t][j]&&!st[j]){
  29.                 st[j] = true;
  30.                 dist[j] = dist[t]+1;
  31.                 q.push(j);
  32.             }
  33.         }
  34.     }
  35. }
  37. int main()
  38. {
  39.     cin >> m >> n;
  40.     getchar();
  41.     for (int i = 1; i <= m; i ++ ){
  42.         string str;
  43.         getline(cin,str);
  44.         stringstream ssin(str);
  45.         int x;
  46.         int cnt=0;
  47.         while(ssin>>x){
  48.             stop[cnt] =x;
  49.             cnt++;
  50.         }
  51.         for (int i = 0; i < cnt; i ++ ){
  52.             for (int j = i+1; j < cnt; j ++ ){
  53.                 g[stop[i]][stop[j]]=true;
  54.             }
  55.         }
  56.     }
  57.     bfs(1);
  58.     if(dist[n]==INF){
  59.         puts("NO");
  60.     }else{
  61.         cout <<max(dist[n]-1,0);
  62.     }
  63. }

903. 昂贵的聘礼

年轻的探险家来到了一个印第安部落里。
在那里他和酋长的女儿相爱了，于是便向酋长去求亲。
酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。
探险家拿不出这么多金币，便请求酋长降低要求。
酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 5000 金币就行了。”
探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。
探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。
不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。
探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。
另外他要告诉你的是，在这个部落里，等级观念十分森严。
地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。
他是一个外来人，所以可以不受这些限制。
但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。
因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从 1 开始进行编号，酋长的允诺也看作一个物品，并且编号总是 1。
每个物品都有对应的价格 P，主人的地位等级 L，以及一系列的替代品 Ti 和该替代品所对应的”优惠” Vi。
如果两人地位等级差距超过了 M，就不能”间接交易”。
你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
输入格式
输入第一行是两个整数 M，N，依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出了 N 个物品的描述。
每个物品的描述开头是三个非负整数 P、L、X，依次表示该物品的价格、主人的地位等级和替代品总数。
接下来 X 行每行包括两个整数 T 和 V，分别表示替代品的编号和”优惠价格”。
输出格式
输出最少需要的金币数。
输入格式

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

输出格式
5250
image.png

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 110,INF = 0x3f3f3f3f;
  9. int n, m;
  10. int g[N][N];
  11. int dist[N],level[N];
  12. bool st[N];
  15. int dijkstra(int down,int up)
  16. {
  17.     memset(dist, 0x3f, sizeof dist);
  18.     memset(st, 0, sizeof st);  // 一定要在这里memset
  19.     dist[0] = 0;
  20.     for (int i = 0; i < n ; i ++ )  //
  21.     {
  22.         int t = -1;
  23.         for (int j = 0; 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.             if(level[j]>=down&&level[j]<=up){
  29.                 dist[j] = min(dist[j], dist[t] + g[t][j]);   
  30.             }
  31.         }
  32.         st[t] = true;
  33.     }
  34.     return dist[1];
  35. }
  37. int main()
  38. {
  39.     scanf("%d%d", &m, &n);
  40.     memset(g, 0x3f, sizeof g);
  41.     for (int i = 1; i <= n; i ++ ){
  42.         int price,cnt;
  43.         cin >> price >> level[i] >> cnt;
  44.         // 建立虚拟源点0号点
  45.         g[0][i] = min(g[0][i],price);
  46.         for (int j = 0; j < cnt; j ++ ){
  47.             int id,value;
  48.             cin >> id >> value;
  49.             g[id][i] = min(g[id][i],value);
  50.         }
  51.     }
  52.     int res=INF;
  53.     for (int i = level[1]-m; i <= level[1]; i ++ ){
  54.         res = min( dijkstra(i,i+m), res);
  55.     }
  56.     cout << res;
  57.     return 0;
  58. }

单源最短路的综合应用

1135. 新年好

重庆城里有 nn 个车站，mm 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 11，他有五个亲戚，分别住在车站 a,b,c,d,ea,b,c,d,e。
过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。
怎样走，才需要最少的时间？
输入格式
第一行：包含两个整数 n,mn,m，分别表示车站数目和公路数目。
第二行：包含五个整数 a,b,c,d,ea,b,c,d,e，分别表示五个亲戚所在车站编号。
以下 mm 行，每行三个整数 x,y,tx,y,t，表示公路连接的两个车站编号和时间。
输出格式
输出仅一行，包含一个整数 TT，表示最少的总时间。
输入样例：
6 6 2 3 4 5 6 1 2 8 2 3 3 3 4 4 4 5 5 5 6 2 1 6 7
输出样例：
21
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;
  11. typedef pair<int, int> PII;
  12. const int N = 5e5+10,INF=0x3f3f3f3f;
  13. vector<PII>h[N];
  14. int n,m;
  15. int dist[6][N],source[6];
  16. bool st[N];
  17. int ans=INF;
  19. int dij(int start,int dist[]){
  20.     memset(dist, 0x3f, N * 4);
  21.     memset(st, 0, sizeof st);
  22.     dist[start] = 0;
  23.     priority_queue<PII,vector<PII>,greater<PII>>heap;
  24.     heap.push({0,start});
  25.     while(!heap.empty()){
  26.         auto t=heap.top();
  27.         heap.pop();
  29.         int ver = t.y;
  30.         int d1 = t.x;
  31.         if(st[ver]){
  32.             continue;
  33.         }
  34.         // 只能在这里标记访问
  35.         st[ver] = true;
  36.         for (int i = 0; i < h[ver].size(); i ++ ){
  37.             int son = h[ver][i].x;
  38.             int d2 = h[ver][i].y;
  39.             if(st[son]){
  40.                 continue;
  41.             }
  42.             if(d1 + d2 < dist[son]){
  43.                 dist[son] = d1+d2;
  44.                 heap.push({d1+d2,son});
  45.             }
  46.         }
  47.     }
  48. }
  49. // 全排列枚举每一种方案
  50. void dfs(int index,int last,int sum){
  51.     if(index>=5){
  52.         ans = min(sum,ans);
  53.     }
  54.     for (int i = 1; i <= 5; i ++ ){
  55.         if(!st[i]){
  56.             st[i] = true;
  57.             dfs(index+1,i,sum+dist[last][source[i]]);
  58.             st[i] = false;
  59.         }
  60.     }
  61. }
  63. int main()
  64. {
  65.     scanf("%d%d", &n, &m);
  66.     source[0]=1;
  67.     for (int i = 1; i <=5; i ++ ){
  68.         cin >> source[i];
  69.     }
  71.     while (m -- )
  72.     {
  73.         int a, b, c;
  74.         scanf("%d%d%d", &a, &b, &c);
  75.         h[a].push_back({b,c});
  76.         h[b].push_back({a,c});
  77.     }
  78.     for (int i = 0; i < 6; i ++ ){
  79.         dij(source[i],dist[i]);
  80.     }
  81.     memset(st, 0, sizeof st);
  82.     dfs(0,0,0);
  83.     cout << ans;
  84.     return 0;
  85. }

340. 通信线路(双端队列求0，1最短路，二分)

在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。
特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。
现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 Li。
电话公司正在举行优惠活动。
农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
输入格式
第 1 行：三个整数 N，P，K。
第 2..P+1 行：第 i+1 行包含三个整数 Ai,Bi,Li。
输出格式
包含一个整数表示最少花费。
若 1 号基站与 N 号基站之间不存在路径，则输出 −1。
输入样例：
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样例：
4

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <deque>
  6. #define x first
  7. #define y second
  8. using namespace std;
  10. typedef pair<int, int> PII;
  11. const int N = 1010;
  12. int n,m,k;
  14. vector<PII>h[N];
  15. bool st[N];
  16. int dist[N];
  17. // 双端队列求0-1最短路
  18. bool check(int mid){
  19.     deque<PII>q;
  20.     memset(st, 0, sizeof st);
  21.     memset(dist, 0x3f, sizeof dist);
  23.     dist[1]=0;
  24.     q.push_back({1,0});
  25.     while(!q.empty()){
  26.         auto t = q.front();
  27.         q.pop_front();
  28.         int x = t.x;
  29.         int d = t.y;
  30.         if(st[x]){
  31.             continue;
  32.         }
  33.         st[x] = true;
  34.         for (int i = 0; i < h[x].size(); i ++ ){
  35.             int j = h[x][i].x;
  36.             int w = h[x][i].y>mid;
  37.             if(d+w<dist[j]){
  38.                 dist[j] = d+w;
  39.                 if(w>0){
  40.                     q.push_back({j,dist[j]});
  41.                 }else{
  42.                     q.push_front({j,dist[j]});
  43.                 }
  44.             }
  45.         }
  46.     }
  48.     return dist[n]<=k;
  49. }
  51. int main()
  52. {
  53.     cin >> n >> m >> k;
  54.     while (m -- ){
  55.         int a,b,c;
  56.         cin >> a >> b>> c;
  57.         h[a].push_back({b,c});
  58.         h[b].push_back({a,c});
  59.     }
  60.     int l=0,r=1e6+1;
  61.     while(l<r){
  62.         int mid = l+r>>1;
  63.         if(check(mid)){
  64.             r = mid;
  65.         }else{
  66.             l = mid+1;
  67.         }
  68.     }
  69.     if(r==1e6+1){
  70.         puts("-1");
  71.     }else{
  72.         cout << r<<endl;
  73.     }
  74. }
  75. /*
  76. 二分原理
  77.     mid 是当除去k条边后最大值是mid的情况下
  78.     看看能不能走到终点
  79.     那么就将大于mid的边设置为1，小于mid的边设置为0，
  80.     看看从1号点到n号点的权值为多少，如果大于k了说明不行，
  81.     如果小于k了说明可以
  82. */

342. 道路与航线（拓扑排序+dij,负权边+正权边）

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。
他想把牛奶送到 T 个城镇，编号为 1∼T。
这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。
每条道路 i 或者航线 i 连接城镇 Ai 到 Bi，花费为 Ci。
对于道路，0≤Ci≤10,000;然而航线的花费很神奇，花费 Ci 可能是负数(−10,000≤Ci≤10,000)。
道路是双向的，可以从 Ai 到 Bi，也可以从 Bi 到 Ai，花费都是 Ci。
然而航线与之不同，只可以从 Ai 到 Bi。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 Ai 到 Bi，那么保证不可能通过一些道路和航线从 Bi 回到 Ai。
由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。
输入格式
第一行包含四个整数 T,R,P,S。
接下来 R 行，每行包含三个整数（表示一个道路）Ai,Bi,Ci。
接下来 P 行，每行包含三个整数（表示一条航线）Ai,Bi,Ci。
输出格式
第 1..T 行：第 i 行输出从 S 到达城镇 i 的最小花费，如果不存在，则输出 NO PATH。
输入样例：
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
输出样例：
NO PATH
NO PATH
5
0
-95
-100

image.png
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #define x first
  6. #define y second
  7. #include <queue>
  9. using namespace std;
  10. typedef pair<int, int> PII;
  11. const int N = 25010,INF = 0x3f3f3f3f;
  12. int n,mr,mp,S;
  13. vector<PII>h[N];
  14. int bid[N],cnt; // bid[i],i号点在哪个小分块当中，cnt总共几个小分块
  15. vector<int>block[N]; // 每个分块中的点
  16. bool st[N];
  17. int din[N]; // 每个分块的入度
  18. int dist[N];
  19. queue<int>q;
  21. void dfs(int u,int id){
  22.     block[id].push_back(u);
  23.     bid[u] = id;
  24.     for (int i = 0; i < h[u].size(); i ++ ){
  25.         int j = h[u][i].x;
  26.         if(!bid[j]){
  27.             dfs(j,id);
  28.         }
  29.     }
  30. }
  32. void dij(int id){
  33.     priority_queue<PII,vector<PII>,greater<PII>>heap;
  34.     for (int i = 0; i < block[id].size(); i ++ ){
  35.         int a = block[id][i];
  36.         heap.push({dist[a],a});
  37.     }
  38.     while(heap.size()){
  39.         auto t = heap.top();
  40.         heap.pop();
  41.         int a = t.y;
  42.         int d = t.x;
  43.         if(st[a]){
  44.             continue;
  45.         }
  46.         st[a] = true;
  48.         for (int i = 0; i < h[a].size(); i ++ ){
  49.             int b = h[a][i].x;
  50.             int c = h[a][i].y;
  51.             if(bid[a]!=bid[b]&&--din[bid[b]]==0){ // 说明这个通过a点可以到达另一个小堆里面
  52.                 q.push(bid[b]);
  53.             }
  54.             if(dist[b]>d+c){
  55.                 dist[b] = d+c;
  56.                 if(bid[a]==bid[b]){
  57.                     heap.push({dist[b],b});
  58.                 }
  59.             }
  60.         }
  61.     }
  62. }
  65. void topsort(){
  66.     memset(dist, 0x3f, sizeof dist);
  67.     dist[S]=0;
  68.     for (int i = 1; i <= cnt; i ++ ){
  69.         if(!din[i]){
  70.             q.push(i);
  71.         }
  72.     }
  73.     while(!q.empty()){
  74.         auto t = q.front();
  75.         q.pop();
  76.         dij(t);
  77.     }
  78. }
  80. int main()
  81. {
  82.     cin >> n >> mr >> mp >> S;
  83.     for (int i = 0; i < mr; i ++ ){
  84.         int a,b,c;
  85.         cin >> a >> b >> c;
  86.         h[a].push_back({b,c});
  87.         h[b].push_back({a,c});
  88.     }
  89.     // 建立各个小分块
  90.     for (int i = 1; i <= n; i ++ ){
  91.         if(!bid[i]){
  92.             dfs(i,++cnt);
  93.         }
  94.     }
  95.     // 读入航线
  96.     for (int i = 0; i < mp; i ++ ){
  97.         int a,b,c;
  98.         cin >> a >> b >> c;
  99.         din[bid[b]]++;
  100.         h[a].push_back({b,c});
  101.     }
  102.     topsort();
  103.     for (int i = 1; i <= n; i ++ ){
  104.         if(dist[i]>INF/2){
  105.             puts("NO PATH");
  106.         }else{
  107.             cout << dist[i]<<endl;
  108.         }
  109.     }
  110. }

341. 最优贸易

C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。
任意两个城市之间最多只有一条道路直接相连。
这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。
但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游
当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。
设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。
在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。
阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
因为阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。
请你告诉阿龙，他最多能赚取多少旅费。
输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。
如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。
输出格式
一个整数，表示答案。
输入样例：
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例：
5
image.png
image.png

  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 n,m;
  10. int d1[N],d2[N];
  11. int mind[N],maxd[N];
  12. vector<int>h1[N];
  13. vector<int>h2[N];
  14. int w[N];
  15. bool st[N];
  17. void spfa(vector<int>h[],int dist[],int type){
  18.     memset(st, 0, sizeof st);
  19.     queue<int>q;
  20.     if(type==0){
  21.         memset(dist, 0x3f, N*4);
  22.         dist[1] = w[1];
  23.         q.push(1);
  24.     }else{
  25.         memset(dist, 0, N*4);
  26.         dist[n] = w[n];
  27.         q.push(n);
  28.     }
  29.     while(!q.empty()){
  30.         int a = q.front();
  31.         q.pop();
  32.         st[a] = false;
  33.         for (int i = 0; i < h[a].size(); i ++ ){
  34.             int b = h[a][i];
  35.             if(type==0){
  36.                 int t = min(w[b],dist[a]);
  37.                 if(t<dist[b]){
  38.                     dist[b]=t;
  39.                     if(!st[b]){
  40.                         q.push(b);
  41.                     }
  42.                 }
  43.             }else{
  44.                 int t = max(w[b],dist[a]);
  45.                 if(t>dist[b]){
  46.                     dist[b]=t;
  47.                     if(!st[b]){
  48.                         q.push(b);
  49.                     }
  50.                 }                
  51.             }
  52.         }
  53.     }
  54. }
  56. int main()
  57. {
  58.     cin >> n >> m;
  59.     for (int i = 1; i <= n; i ++ ){
  60.         cin >> w[i];
  61.     }
  62.     while (m -- ){
  63.         int a,b,t;
  64.         cin >> a >> b >> t;
  65.         h1[a].push_back(b);
  66.         h2[b].push_back(a);
  67.         if(t==2){
  68.             h1[b].push_back(a);
  69.             h2[a].push_back(b);            
  70.         }
  71.     }
  72.     spfa(h1,mind,0); // 从1号点走到k的最小值
  73.     spfa(h2,maxd,1); // 从n号点走的k的最大值
  74.     int res=0;
  75.     for (int i = 1; i <= n; i ++ ){
  76.         res = max(maxd[i]-mind[i],res);
  77.     }
  78.     cout << res;
  79. }

差分约束

image.pngimage.png
image.png

1169. 糖果

幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。
但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。
幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入格式
输入的第一行是两个整数 N,K。
接下来 K 行，表示分配糖果时需要满足的关系，每行 3 个数字 X,A,B。
如果 X=1．表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。
如果 X=2，表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
如果 X=3，表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。
如果 X=4，表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
如果 X=5，表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
小朋友编号从 1 到 N。
输出格式
输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。
输入样例：
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
输出样例：
11

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <stack>
  6. #define x first
  7. #define y second
  8. typedef long long LL;
  10. using namespace std;
  11. typedef pair<int, int> PII;
  13. const int N = 1e5+10;
  14. int n,m;
  15. vector<PII>h[N];
  16. LL dist[N];
  17. bool st[N];
  18. int cnt[N];
  20. bool spfa(){
  21.     // 因为要判断是否有环，所以用stack能更快地发现环
  22.     memset(st, 0, sizeof st);
  23.     // 求最小糖果数量，求最长路
  24.     memset(dist, -0x3f, sizeof dist);
  25.     dist[0]=0;
  26.     stack<int>s;
  27.     s.push(0);
  28.     while(!s.empty()){
  29.         int a = s.top();
  30.         s.pop();
  31.         st[a]=false;
  32.         for (int i = 0; i < h[a].size(); i ++ ){
  33.             int b = h[a][i].x;
  34.             int c = h[a][i].y;
  35.             if(dist[a]+c>dist[b]){
  36.                 dist[b] = dist[a]+c;
  37.                 cnt[b]++;
  38.                 // 存在环了，如果无环，一个点最多被更新n-1次
  39.                 if(cnt[b]>=n){
  40.                     return false;
  41.                 }
  42.                 if(!st[b]){
  43.                     st[b] = true;
  44.                     s.push(b);
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     return true;
  50. }
  53. int main()
  54. {
  55.     cin >> n >> m;
  56.     // 建立超级源点，最少数量必须是1
  57.     for (int i = 1; i <= n; i ++ ){
  58.         h[0].push_back({i,1});
  59.     }
  60.     for (int i = 0; i < m; i ++ ){
  61.         int t,a,b;
  62.         cin >> t >> a>>b;
  63.         if(t==1){
  64.             h[a].push_back({b,0});
  65.             h[b].push_back({a,0});
  66.         }else if(t==2){
  67.             h[a].push_back({b,1});
  68.         }else if(t==3){
  69.             h[b].push_back({a,0});
  70.         }else if(t==4){
  71.             h[b].push_back({a,1});
  72.         }else{
  73.             h[a].push_back({b,0});
  74.         }
  75.     }
  76.     bool res = spfa();
  77.     if(res){
  78.         LL ans = 0;
  79.         for (int i = 1; i <= n; i ++ ){
  80.             ans +=dist[i];
  81.         }
  82.         cout << ans;
  83.     }else{
  84.         cout << -1 ;
  85.     }
  86. }

362.区间

给定 n 个区间 [ai,bi] 和 n 个整数 ci。
你需要构造一个整数集合 Z，使得 ∀i∈[1,n]，Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。
求这样的整数集合 Z 最少包含多少个数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,ci。
输出格式
输出一个整数表示结果。
数据范围
1≤n≤50000,
0≤ai,bi≤50000,
1≤ci≤bi−ai+1
输入样例：
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出样例：
6

这道题题意有点难理解，注意一定是集合

image.png

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. const int N = 50010, M = 150010;
  10. int n;
  11. int h[N], e[M], w[M], ne[M], idx;
  12. int dist[N];
  13. int q[N];
  14. bool st[N];
  16. void add(int a, int b, int c)
  17. {
  18.     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
  19. }
  21. void spfa()
  22. {
  23.     memset(dist, -0x3f, sizeof dist);
  24.     dist[0] = 0;
  25.     st[0] = true;
  26.     int hh = 0, tt = 1;
  27.     q[0] = 0;
  29.     while (hh != tt)
  30.     {
  31.         int t = q[hh ++ ];
  32.         if (hh == N) hh = 0;
  33.         st[t] = false;
  35.         for (int i = h[t]; ~i; i = ne[i])
  36.         {
  37.             int j = e[i];
  38.             if (dist[j] < dist[t] + w[i])
  39.             {
  40.                 dist[j] = dist[t] + w[i];
  41.                 if (!st[j])
  42.                 {
  43.                     q[tt ++ ] = j;
  44.                     if (tt == N) tt = 0;
  45.                     st[j] = true;
  46.                 }
  47.             }
  48.         }
  49.     }
  50. }
  52. int main()
  53. {
  54.     scanf("%d", &n);
  56.     memset(h, -1, sizeof h);
  57.     for (int i = 1; i < N; i ++ )
  58.     {
  59.         add(i - 1, i, 0);
  60.         add(i, i - 1, -1);
  61.     }
  63.     for (int i = 0; i < n; i ++ )
  64.     {
  65.         int a, b, c;
  66.         scanf("%d%d%d", &a, &b, &c);
  67.         a ++, b ++ ;
  68.         add(a - 1, b, c);
  69.     }
  71.     spfa();
  73.     printf("%d\n", dist[50001]);
  75.     return 0;
  76. }

1170. 排队布局

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。
农夫约翰有 N 头奶牛，编号从 1 到 N，沿一条直线站着等候喂食。
奶牛排在队伍中的顺序和它们的编号是相同的。
因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上
如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 L。
另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D。
给出 ML 条关于两头奶牛间有好感的描述，再给出 MD 条关于两头奶牛间存有反感的描述。
你的工作是：如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。
输入格式
第一行包含三个整数 N,ML,MD。
接下来 ML 行，每行包含三个正整数 A,B,L，表示奶牛 A 和奶牛 B 至多相隔 L 的距离。
再接下来 MD 行，每行包含三个正整数 A,B,D，表示奶牛 A 和奶牛 B 至少相隔 D 的距离。
输出格式
输出一个整数，如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；否则，输出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。
数据范围
2≤N≤1000,
1≤ML,MD≤10^4,
1≤L,D≤10^6
输入样例：
4 2 1
1 3 10
2 4 20
2 3 3
输出样例：
27
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. typedef pair<int, int> PII;
  12. const int N = 1010,INF = 0x3f3f3f3f;
  13. vector<PII>h[N];
  14. bool st[N];
  15. int cnt[N];
  16. int dist[N];
  17. int n,m,k;
  19. bool spfa(int size){
  20.     memset(st, 0, sizeof st);
  21.     memset(dist ,0x3f, sizeof dist);
  22.     memset(cnt, 0, sizeof cnt);
  23.     queue<int>q;
  24.     for (int i = 1; i <= size; i ++ ){
  25.         q.push(i);
  26.         st[i] = true;
  27.         dist[i] = 0;
  28.     }
  29.     while(!q.empty()){
  30.         int t = q.front();
  31.         q.pop();
  32.         st[t] = false;
  33.         for (int i = 0; i < h[t].size(); i ++ ){
  34.             int b = h[t][i].x;
  35.             int c = h[t][i].y;
  36.             if(dist[b]>dist[t]+c){  // 求最短路
  37.                 dist[b] = dist[t]+c;
  38.                 cnt[b]++;
  39.                 if(cnt[b]>n){
  40.                     return false;
  41.                 }
  42.                 if(!st[b]){
  43.                     st[b] = true;
  44.                     q.push(b);
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     return true;
  50. }
  52. int main()
  53. {
  54.     cin >> n >> m >> k;
  55.     for (int i = 1; i < n; i ++ ){
  56.         h[i+1].push_back({i,0});
  57.     }
  58.     while (m -- ){
  59.         int a,b,c;
  60.         cin >> a >> b >> c;
  61.         if(a>b){
  62.             swap(a,b);
  63.         }
  64.         h[a].push_back({b,c});
  65.     }
  66.     while (k -- ){
  67.         int a,b,c;
  68.         cin >> a >> b >> c;
  69.         if(a>b){
  70.             swap(a,b);
  71.         }        
  72.         h[b].push_back({a,-c});
  73.     }
  74.     if(!spfa(n)){  // 把n个点全放进去，看看有没负环
  75.         puts("-1");
  76.     }else{
  77.         spfa(1);  // 看看1号点能不能到n号点
  78.         if(dist[n]==INF){
  79.             puts("-2");
  80.         }else{
  81.             cout << dist[n];
  82.         }
  83.     }
  84. }

最近公共祖先

image.png
image.png

1172. 祖孙询问

给定一棵包含 nn 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n1∼n。
有 mm 个询问，每个询问给出了一对节点的编号 xx 和 yy，询问 xx 与 yy 的祖孙关系。
输入格式
输入第一行包括一个整数 表示节点个数；
接下来 nn 行每行一对整数 aa 和 bb，表示 aa 和 bb 之间有一条无向边。如果 bb 是 −1−1，那么 aa 就是树的根；
第 n+2n+2 行是一个整数 mm 表示询问个数；
接下来 mm 行，每行两个不同的正整数 xx 和 yy，表示一个询问。
输出格式
对于每一个询问，若 xx 是 yy 的祖先则输出 11，若 yy 是 xx 的祖先则输出 22，否则输出 00。

image.png image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  6. using namespace std;
  8. const int N = 4e4+10;
  9. int n,m,root;
  10. int f[N][16],depth[N];
  11. vector<int>h[N];
  12. bool st[N];
  13. void bfs(int u){
  14.     queue<int>q;
  15.     depth[0] = 0;
  16.     depth[u] = 1;
  17.     q.push(u);
  18.     st[u] = true;
  19.     while(!q.empty()){
  20.         int a = q.front();
  21.         q.pop();
  22.         for (int i = 0; i < h[a].size(); i ++ ){
  23.             int b = h[a][i];
  24.             if(!st[b]){
  25.                 st[b] = true;
  26.                 q.push(b);
  28.                 depth[b] = depth[a]+1;
  29.                 // 倍增求其祖先
  30.                 f[b][0] = a;
  31.                 for (int k = 1; k <= 15; k ++ ){
  32.                     f[b][k] = f[f[b][k-1]][k-1];
  33.                 }
  34.             }
  35.         }
  36.     }
  37. }
  39. int lca(int a,int b){
  40.     // a的层数更深
  41.     if(depth[a]<depth[b]){
  42.         swap(a,b);
  43.     }
  44.     // 先跳到同一层
  45.     for (int k = 15; k >=0; k -- ){
  46.         if(depth[f[a][k]]>=depth[b]){
  47.             a = f[a][k];
  48.         }
  49.     }
  50.     // 如果两者相等了
  51.     if(a==b){
  52.         return a;
  53.     }
  54.     // 再跳到公共祖先的下一层，
  55.     for (int k = 15; k >=0; k -- ){
  56.         if(depth[f[a][k]]!=depth[f[b][k]]){
  57.             a = f[a][k];
  58.             b = f[b][k];
  59.         }
  60.     }
  61.     return f[a][0];
  62. }
  64. int main()
  65. {
  66.     cin >> n ;
  67.     for (int i = 0; i < n; i ++ ){
  68.         int a,b;
  69.         cin >> a >> b;
  70.         if(b==-1){
  71.             root = a;
  72.         }else{
  73.             h[a].push_back(b);
  74.             h[b].push_back(a);
  75.         }
  76.     }
  77.     bfs(root);
  79.     cin >> m;
  80.     while (m -- ){
  81.         int a,b;
  82.         cin >> a >> b;
  83.         int p = lca(a,b);
  84.         if(p==a){
  85.             puts("1");
  86.         }else if(p==b){
  87.             puts("2");
  88.         }else{
  89.             puts("0");
  90.         }
  91.     }
  92. }

1171. 距离

给出 n 个点的一棵树，多次询问两点之间的最短距离。
注意：
边是无向的。
所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；
下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行，对于每次询问，输出一行询问结果。
输入样例1：
2 2
1 2 100
1 2
2 1
输出样例1：
100
100
输入样例2：
3 2
1 2 10
3 1 15
1 2
3 2
输出样例2：
10
25
image.png
image.png
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. typedef pair<int, int> PII;
  12. const int N = 4e4+10;
  13. int n,m,root;
  14. vector<PII>h[N];
  15. vector<PII>query[N]; // x存另外一个点,y存查询编号
  16. int res[N];
  17. int d[N];  // i节点到父节点的距离
  18. int st[N];
  19. int p[N];
  21. int find(int x)  // 并查集
  22. {
  23.     if (p[x] != x) p[x] = find(p[x]);
  24.     return p[x];
  25. }
  28. void dfs(int u,int fa){
  29.     for (int i = 0; i < h[u].size(); i ++ ){
  30.         int son = h[u][i].x;
  31.         int w = h[u][i].y;
  32.         if(son==fa){
  33.             continue;
  34.         }
  35.         d[son] = d[u] + w;
  36.         dfs(son,u);
  37.     }
  38. }
  40. void tarjan(int u){
  41.     st[u] = 1;
  42.     for (int i = 0; i < h[u].size(); i ++ ){
  43.         int son = h[u][i].x;
  44.         if(st[son]){
  45.             continue; 
  46.         }
  47.         tarjan(son);
  48.         p[son] = u;
  49.     }
  50.     for(auto t:query[u]){
  51.         int b = t.x;
  52.         int index = t.y;
  53.         if(st[b]==2){
  54.             int fab = find(b);
  55.             res[index] = d[u]+d[b]-2*d[fab];
  56.         }
  57.     }
  58.     st[u] = 2;
  59. }
  61. int main()
  62. {
  63.     cin >> n >>m;
  64.     for (int i = 0; i < n-1; i ++ ){
  65.         int a,b,c;
  66.         cin >> a >> b >>c;
  67.         h[a].push_back({b,c});
  68.         h[b].push_back({a,c});
  69.     }
  71.     for (int i = 0; i < m; i ++){
  72.         int a,b;
  73.         cin >> a >> b;
  74.         query[a].push_back({b,i});
  75.         query[b].push_back({a,i});
  76.     }
  78.     for (int i = 1; i <= n; i ++ ){
  79.         p[i] = i;
  80.     }
  82.     dfs(1,-1);
  83.     tarjan(1);
  85.     for (int i = 0; i < m; i ++ ){
  86.         cout << res[i] <<endl;
  87.     }
  88. }

有向图的强连通分量

1174. 受欢迎的牛

每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。
这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
输入格式
第一行两个数 N,M；
接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。
输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
数据范围
1≤N≤10^4,
1≤M≤5×10^4
输入样例：
3 3
1 2
2 1
2 3
输出样例：
1
样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。

image.png
image.png
image.png
image.png

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N = 10010, M = 50010;
  6. int n, m;
  7. int h[N], w[M], e[M], ne[M], idx; // 邻接表一套
  8. // dfn[u] 存的是遍历到u的时间戳
  9. // low[u]存的是从u出发，遍历子树，所能遍历到的最小的时间戳
  10. //timestamp 就是时间戳
  11. int dfn[N], low[N], timestamp;
  12. int stk[N], top; // 栈，和栈顶元素索引
  13. bool in_stk[N]; // 是否在栈中
  14. //id[u]表示u的强连通分量的编号，scc_cnt表示强连通分量的编号
  15. // size_scc[u]表示编号为u强连通分量中点的数量
  16. int id[N], scc_cnt, size_scc[N];
  17. int dout[N];// 记录新图中每个点（也就是原图每个连通分量）的出度
  19. void add(int a, int b){
  20.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
  21. }
  23. void tarjan(int u){
  24.     //当前点的时间戳
  25.     dfn[u] = low[u] = ++ timestamp;
  26.     // 加入栈中
  27.     stk[++ top] = u, in_stk[u] = true;
  29.     //遍历u点的所有邻点
  30.     for(int i = h[u]; ~i; i = ne[i]){
  31.         int j = e[i];
  32.         if(!dfn[j]){//如果没有遍历过
  33.             tarjan(j); // 遍历它
  34.             low[u] = min(low[u], low[j]);
  35.         }
  36.         // 当前点在栈当中
  37.         else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
  38.     }
  40.     if(dfn[u] == low[u]){
  41.         ++ scc_cnt; // 更新强连通分量的编号
  42.         int y;
  43.         do{
  44.             y = stk[ top--]; //不断取出栈内元素
  45.             in_stk[y] = false;
  46.             id[y] = scc_cnt; //y元素所属的连通块编号
  47.             size_scc[scc_cnt] ++; //该连通块内包含的点数
  48.         }while(y != u); // 直到y不等于u
  49.     }
  51. }
  53. int main(){
  54.     cin >> n >> m;
  55.     memset(h, -1, sizeof h);
  56.     while(m --){
  57.         int a, b;
  58.         cin >> a >> b;
  59.         add(a, b);
  60.     }
  62.     for(int i = 1; i <= n; i ++){
  63.         if(!dfn[i])
  64.             tarjan(i);
  65.     }
  67.     // 建有向无环图
  68.     // 统计在新图中所有点的出度
  69.     for(int i = 1; i <= n; i ++){
  70.         for(int j = h[i]; ~j; j = ne[j]){
  71.             int k = e[j];
  72.             int a = id[i]; //a表示i所在连通分量的编号
  73.             int b = id[k]; // b表示k所在连通分量的编号
  74.             //如果点i和点k不在同一个连通块
  75.             // dout存的是出度，因为本题只需要出度
  76.             //在其他题目中，可能是要建边，因为这里是构造有向无环图
  77.             if(a != b) dout[a] ++; // 从a走到b，a的出度++
  78.         }
  79.     }
  81.     // 和本题有关的部分：
  82.     // zeros是统计在新图中，出度为0的点的个数
  83.     // sum表示满足条件的点（最受欢迎的奶牛）的个数
  84.     int zeros = 0, sum = 0;
  85.     for(int i = 1; i <= scc_cnt; i ++){
  86.         if(!dout[i]){
  87.             zeros ++;
  88.             sum += size_scc[i];
  89.             if(zeros > 1){
  90.                 sum = 0;
  91.                 break;
  92.             }
  93.         }
  94.     }
  95.     cout << sum << endl;
  96. }