avatar
fireworks99
keep hungry keep foolish

POJ 1797 Heavy Transportation

Description

n个点,m个关于边的叙述(边的权值代表路的最大承载量)

求从1到n,路上的最大承载量

题目链接 http://poj.org/problem?id=1797

思路

最短路变形

最大化最小值:

两条路:

  1. 当前直达

  2. 中转

    择优(承载量大的那条)

这里有个相反的:最小化最大值: https://fireworks99.github.io/2019/03/28/POJ-2253-Frogger/

Code of Dijkstra

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define check cout << "Let's check : " << '\n'; const int INF = 0x3f3f3f3f; const int N = 1010;///点 的上限 int n, m; bool vis[N];///是否用过它 int mp[N][N]; int dis[N]; void dijkstra(int start) { memset(vis, 0, sizeof(vis)); memset(dis, -1, sizeof(dis)); for(int i = 1; i <= n; ++i)///邻接表下的dijkstra要先处理start dis[i] = mp[start][i]; vis[start] = 1; for(int i = 1; i <= n; ++i) { int mmax = -1; int pos; for(int j = 1; j <= n; ++j)///++j写成了++i...卡了半天 if(!vis[j] && dis[j] > mmax) { pos = j; mmax = dis[j]; } vis[pos] = 1; for(int j = 1; j <= n; ++j) { if(vis[j])///用过的点直接跳过 continue; if(dis[j] < min(dis[pos], mp[pos][j])) dis[j] = min(dis[pos], mp[pos][j]); } } } int main() { int t; cin >> t; int tem = t; while(t--) { scanf("%d%d", &n, &m); int b, c, d; memset(mp, -1, sizeof(mp));///邻接表要初始化 for(int i = 0; i < m; ++i) { scanf("%d%d%d", &b, &c, &d); mp[b][c] = mp[c][b] = d; } dijkstra(1); printf("Scenario #%d:\n%d\n\n", tem - t, dis[n]); } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

Code of spfa

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int N = 1010;///点 的上限 int n, m; bool vis[N];///vis[i] = 1表示点在队列里,0表示不在 int dis[N];///从起点到某点(答案意义上的)“最短”距离 int cnt, head[N]; struct edge { int from, to, w, pre; } a[N * N]; void add(int from, int to, int w) { a[cnt].from = from; a[cnt].to = to; a[cnt].w = w; a[cnt].pre = head[from]; head[from] = cnt; cnt++; a[cnt].to = from; a[cnt].from = to; a[cnt].w = w; a[cnt].pre = head[to]; head[to] = cnt; cnt++; } void spfa(int start) { memset(vis, 0, sizeof(vis)); memset(dis, -1, sizeof(dis)); dis[start] = INF; vis[start] = 1; queue<int> q; q.push(start); while(q.size()) { int first = q.front();///当前检测点用作“中转点” q.pop(); vis[first] = 0; for(int i = head[first]; ~i; i = a[i].pre) { int t = a[i].to; ///最大化最小值:选择(“最短直接”到)与(中转到)更大的那条路 ///即有多条路时选最优的 if(dis[t] < min(dis[first], a[i].w)) { dis[t] = min(dis[first], a[i].w); q.push(t); vis[t] = 1; } } } } int main() { int t; cin >> t; int tem = t; while(t--) { cnt = 0; memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); int b, c, d; for(int i = 0; i < m; ++i) { scanf("%d%d%d", &b, &c, &d); add(b, c, d); } spfa(1); printf("Scenario #%d:\n%d\n\n", tem - t, dis[n]); } return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy