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;
}

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;
}