Heavy Transportation(POJ 1793)
写这题被坑了好几次，这题解法思路就是在最短路中用权值最大的边为基础不断更新可以用朴素dijkstra，堆优化dijkstra, spfa，kurskal等。
注意：1.数据量大要用cin,cout会TLE 2.图是无向图不是有向图 3.输出格式记得每组答案后面有两回车
| ac代码如下 | |
|---|---|
1.朴素版Dijkstra
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//求边权的最小值最大
const int N = 1010, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(int n)
{
memset(st, false, sizeof st);
memset(dist, -1, sizeof dist); //所有1到x的距离设置负无穷
dist[1] = INF;
for(int i = 1; i < n; ++i)
{
int t = -1;
for(int j = 1; j <= n; ++j)
if(!st[j] && (t == -1 || dist[j] > dist[t])) //最小的最大,每个都最大，最小的一定大
t = j;
st[t] = true;
for(int j = 1; j <= n; ++j)
dist[j] = max(dist[j], min(dist[t], g[t][j])); //从1到t,再从t到j可能更优
}
return dist[n];
}
int main()
{
int T;
scanf("%d", &T);
for(int i = 1; i <= T; ++i)
{
int n, m;
scanf("%d%d", &n, &m);
memset(g, -1, sizeof g); //边设置为负无穷
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = max(g[b][a], c); //无向边 （max防重边,这题没重边,可以去掉）
}
printf("Scenario #%d:\n%d\n\n", i, dijkstra(n));
}
return 0;
}
朴素版Dijkstra耗时如下
2.堆优化版Dijkstra
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
//求边权的最小值最大
typedef pair<int, int> PII;
const int N = 1010, M = 1e5, INF = 0x3f3f3f3f;
int e[M], w[M], ne[M], h[N], idx;
int dist[N]; //保存从1到n的所有边中最小的边最大
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void init()
{
idx = 0;
memset(h, -1, sizeof h);
}
int dijkstra(int n)
{
memset(dist, -1, sizeof dist); //先将所有边初始化为-1
memset(st, false, sizeof st);
dist[1] = INF; //起点设为最大
priority_queue<PII> heap;
heap.push({dist[1], 1});
while(!heap.empty())
{
int key = heap.top().second;
heap.pop();
if(st[key]) continue; // 已经用dist[key]更新过，无需重复进行
st[key] = true;
for(int i = h[key]; i != -1; i = ne[i])
{
int &j = e[i];
if(dist[j] < min(dist[key], w[i])) //最小的最大,每个都尽量大，最小的一定大 //从1->t->j可能比1->j更优解
{
dist[j] = min(dist[key], w[i]);
heap.push({dist[j], j});
}
}
}
return dist[n];
}
int main()
{
int T;
scanf("%d", &T);
for(int i = 1; i <= T; ++i)
{
init(); //链式向前星初始化
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c); //无向边是特殊的有向边
}
printf("Scenario #%d:\n%d\n\n", i, dijkstra(n));
}
return 0;
}
看起来堆优化版Dijkstra效果不佳啊
3.Kruskal版
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, M = 1e5, INF = 0x3f3f3f3f;
struct Edge{ //存边,重载运算符好从小到大排序
int u, v, w;
bool operator < (const Edge& t) const {
return w > t.w;
}
}edges[M];
int p[N];
int find(int u){ //并查集
return u == p[u] ? p[u] : p[u] = find(p[u]);
}
int main()
{
int T;
scanf("%d", &T);
for(int i = 1; i <= T; ++i)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) p[i] = i;
for(int j = 0; j < m; ++j)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[j] = {a, b, c};
}
//kruskal
sort(edges, edges + m); //边从大到小排序
int ans = INF;
for(int j = 0; j < m && find(1) != find(n); ++j) //不连通 联通说明一定是选从大到小的边
{
int &u = edges[j].u, &v = edges[j].v, &w = edges[j].w;
int p1 = find(u), p2 = find(v);
if(p1 != p2) //两个顶点不连通,那么一定会被一条最或多条大的边连起来
{
p[p1] = p2;
ans = min(ans, w); //1和n联通 用到的最小边便是答案， 其他联通用的边一定 >= ans
}
}
printf("Scenario #%d:\n%d\n\n", i, ans);
}
return 0;
}
Kruskal还算快,写起来也方便
4.SPFA版本
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
//求边权的最小值最大
const int N = 1010, M = 1e5 + 10;
int dist[N];
bool st[N];
int e[M], w[M], ne[M], h[N], idx;
void init()
{
idx = 0;
memset(h, -1, sizeof h);
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa(int n)
{
memset(dist, -1, sizeof dist);
memset(st, false, sizeof st); //存储顶点是否在队列
dist[1] = 1e9;
queue<int> q;
q.push(1);
st[1] = true;
while(!q.empty())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int &j = e[i];
if(dist[j] < min(dist[t], w[i]))
{
dist[j] = min(dist[t], w[i]);
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
int T;
scanf("%d", &T);
for(int i = 1; i <= T; ++i)
{
int n, m;
scanf("%d%d", &n, &m);
init();
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
printf("Scenario #%d:\n%d\n\n", i, spfa(n));
}
return 0;
}
好吧，快速最短路算法有点大失所望了
Tips: 朝着区域赛冲!!!!!!!!!