有关最短路上的第k小/大值的总结
2024-09-20 20:48:04
1.USACO08JAN Telephone Lines 题面
由于问的是最大值最小,所以二分加验证就好了
比较显然的,题干问的是第k+1长的路最短;
那么二分答案是正确的方向;
但是怎么验证?
我们可以将所有边权大于二分的答案的边视为边权是1,否则看成0;
然后从1~n跑最短路,如果答案大于二分的答案那么就不成立,否则成立;
这种思维比较重要,代码还是很简单的;
#include <bits/stdc++.h>
using namespace std;
int head[2000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[2000010];
int n,p,k;
int dis[100010],vis[100010];
bool SPFA(int x)
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
memset(vis,0,sizeof(vis));
q.push(1);
while(q.size()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+(star[i].w>x)){
dis[v]=dis[u]+(star[i].w>x);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
if(dis[n]<=k) return 1;
else{
return 0;
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
}
int l=0,r=1000000;
while(l<r){
int mid=(l+r)/2;
if(SPFA(mid)){
r=mid;
}
else{
l=mid+1;
}
}
if(l==1000000) l=-1;
cout<<l<<endl;
}
这道题很上一道题不太一样,所求的是对于每种方案去掉前k大边后的最短路;
首先由于k很小,可以进行分层图;
第i层图表示目前已经删去了i条边的最短路;
对于点对(i,j)在任意层中边权是w;从第i层到第i+1层的边权是0;
然后堆优化+dijkstra就可以了;
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
int S,T;
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,S));
dis[S]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
cin>>S>>T;
++S;++T;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
++u; ++v;
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,0);
star[++cnt].add(j*n+v,(j+1)*n+u,0);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+T,n*30+T,0);
}
dijkstra();
cout<<dis[n*30+T];
}
和上一道题思路一样,都是分层图,但连接第i层和第i+1层的边权不再是0,而是w/2;
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,1));
dis[1]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,w/2);
star[++cnt].add(j*n+v,(j+1)*n+u,w/2);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+n,n*30+1,0);
}
dijkstra();
cout<<dis[n*30+1];
}
4.[USACO09FEB]改造路Revamping Trails
思路重复,代码几乎一样,就不多说了;把这到题放到这里的原因是想告诉大家,USACO的题要好好做啊,很多省选题都来源于此;
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,1));
dis[1]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,0);
star[++cnt].add(j*n+v,(j+1)*n+u,0);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+n,n*30+1,0);
}
dijkstra();
cout<<dis[n*30+1];
}
最新文章
- linux 查看文件大小
- SQL Server 解读【已分区索引的特殊指导原则】(3) - 非聚集索引分区
- Bootstrap<;基础十四>; 按钮下拉菜单
- POJ2309 -- BST
- java多线程系列3-线程同步
- SVN:通过Client端打tag
- Groovy 数组操作
- U盘安装win7+CentOS7双系统
- AWK----awk与shell交互
- oracle数据库与实例
- Spring MVC 使用介绍(八)—— 类型转换
- druid 连接池加密算法
- mybatis中<;foreach>;标签的使用
- 使goroutine同步的方法总结
- 理解BFC
- 【noip 2012】提高组Day1T3.开车旅行
- C语言 &#183; 超级玛丽
- vue style 的scoped 使用
- open suse linux 磁盘分区
- IDEA如何把写好的java文件/项目打包成一个jar的文件