$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n$ 个点 $m$ 条边的无重边无自环的无向图。
点的编号为 $1 \\sim n$。
现在,要从点 $1$ 到点 $n$ 运货。
已知每条边的最大承重,请你计算一次最多可以运多少货物。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行三个整数 $a,b,c$,表示点 $a$ 和点 $b$ 之间有一条无向边,最大承重为 $c$。
输出格式
每组数据先输出一行 Scenario #x
,其中 $x$ 是组别编号(从 $1$ 开始)。
然后一行,输出一个整数,表示一次性最多可运货物数量。
最后输出一个空行。
数据范围
$1 \\le T \\le 10$,
$1 \\le n \\le 1000$,
$1 \\le m \\le \\frac{n(n-1)}{2}$,
$1 \\le a,b \\le n$,
$1 \\le c \\le 10^6$。
保证一定有解。
输入样例:
1
3 3
1 2 3
1 3 4
2 3 5
输出样例:
Scenario #1:
4
思路
- 思想同青蛙题目,然而此题是求
最大化最小值
;- 若用
最短路
来解决,此时dist
数组初始化为$-\infty$或$0$,起点的$dist[start]$初始化为$+\infty$,在后续操作时每次寻找未标记结点中dist最大的
结点;- 假设起点是$a$,终点是$b$,假设中间途径$c$点,其中
dist[i]
表示从起点$a$出发到达任意一点$i$的中间任意两点的最小距离的最大值
,此时$\color{Green}{dist[b]=max(dist[b],min(dist[c],val[c][b]))}$,而青蛙题目中,表示的是$\color{Magenta}{dist[b]=min(dist[b],max(dist[c],val[c][b]))}$- 若用
最小生成树
的思想,该题则将边从大到小枚举,当起点与终点连通时,输出该结果,注意由于边数较多
采用该方法会卡输入,要用scanf
读入所有边;- 最短路之
最小化最大值
模型(例题:青蛙),最短路之最大化最小值
模型(例题:货物运输)- $Poj$会卡输入
代码
- $Dijkstra$(朴素版)
// Problem: 货物运输
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4244/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-22 16:51:34
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int t;
int n,m;
int val[MAXN][MAXN];
int vis[MAXN];
int dist[MAXN];
void Dijkstra(int start)
{
memset(vis,0,sizeof(vis));
//此处初始化为-inf或0
memset(dist,0,sizeof(dist));
dist[start]=inf;//注意起点初始化为inf
for(int i=1;i<=n-1;i++)//重复进行n-1次
{
int pos=-1;//找到未标记结点中dist最大的
for(int j=1;j<=n;j++)
if(vis[j]==0&&(pos==-1||dist[j]>dist[pos]))//此处有修改
pos=j;
vis[pos]=1;
for(int j=1;j<=n;j++)
dist[j]=max(dist[j],min(val[pos][j],dist[pos]));
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
cin >> t;
while(t--)
{
cin >> n >> m;
memset(val,0,sizeof(val));//记得清空val数组
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
val[a][b]=val[b][a]=c;
}
Dijkstra(1);
printf("Scenario #%d:\n%d\n\n",Cas++,dist[n]);
}
return 0;
}
- $Dijkstra$(堆优化版)
// Problem: 货物运输
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4244/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-22 16:51:34
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 1010
#define MAXM 1000010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int t;
int n,m;
int vis[MAXN];
int dist[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
void Dijkstra(int start)
{
memset(vis,0,sizeof(vis));
//此处初始化为-inf或0
memset(dist,0,sizeof(dist));
dist[start]=inf;//注意起点初始化为inf
priority_queue<PII> q;
q.push({inf,start});//把起点压入优先队列中
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)//当前点已走过
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]<min(temp_dis,val[i]))
{
dist[j]=min(temp_dis,val[i]);
q.push({dist[j],j});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
cin >> t;
while(t--)
{
cin >> n >> m;
memset(head,-1,sizeof(head));
idx=0;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c),add(b,a,c);//双向边
}
Dijkstra(1);
printf("Scenario #%d:\n%d\n\n",Cas++,dist[n]);
}
return 0;
}
- $Kruskal$(最小生成树)
// Problem: 货物运输
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4244/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-22 16:51:34
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 1010
#define MAXM 1000010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int t;
int n,m;
int fa[MAXN];
struct Node{
int start_;
int end_;
int dist;
}v[MAXM];
int cmp(Node a,Node b)
{
return a.dist>b.dist;//此处从大到小排序
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
fa[fx]=fy;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i=1;i<=n;i++)
fa[i]=i;
//该题会卡最小生成树的输入
for(int i=0;i<=m-1;i++)
scanf("%d %d %d",&v[i].start_,&v[i].end_,&v[i].dist);
sort(v,v+m,cmp);
for(int i=0;i<m;i++)
{
join(v[i].start_,v[i].end_);
if(find(1)==find(n))
{
printf("Scenario #%d:\n%d\n\n",Cas++,v[i].dist);
break;
}
}
}
return 0;
}