[分层图] 分层图两例

Telephone Line

求一条路径，使第$k+1$大的边尽量小 即前$k$大的边都被免费掉了，剩下的最大的边付费，要求最小

先把注意写在前面：不合法输出-1

法一

二分

$>mid$的边不缴费，$\le mid$的边缴费 分别记为0/1，求最短路，小于$k$合法

求最短路随便用个算法就能过了

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e4+5; int n,p,k,l=1,r,ans; int tot,first[N],nxt[N<<1],aim[N<<1],wei[N<<1],dis[N]; bool vis[N]; void ljb(int u,int v,int w){ ++tot; nxt[tot]=first[u]; first[u]=tot; wei[tot]=w; aim[tot]=v; return; } bool check(int mid){ priority_queue<pair<int,int> >q; memset(dis,0x3f,sizeof dis); memset(vis,false,sizeof vis); dis[1]=0; q.push(make_pair(0,1)); while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u]) continue; vis[u]=true; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(dis[v]>dis[u]+(wei[e]>mid)){ dis[v]=dis[u]+(wei[e]>mid); q.push(make_pair(-dis[v],v)); } } } return dis[n]<=k; } int main(){ n=in,p=in,k=in; for(int i=1;i<=p;++i){ int u=in,v=in,w=in; ljb(u,v,w); ljb(v,u,w); r=max(r,w); } while(l<=r){ int mid=l+r>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } if(!ans) puts("-1"); else printf("%d\n",ans); return 0; }

法二

DP

就DP呗，记录状态f[u][p]表示到u，免p条边的最小付费 边界f[1][i]=0 状移： $$\begin{gathered} f_{v,p}=\min \{\max \{f_{u,p},w_{u\to v}\}\} \\ {f}_{v,p+1}=\min \{f_{u,p}\} \end{gathered}$$ 考虑状移方式：不能是遍历图，会重边 考虑分层图：遍历一堆图

分层图就是将原图按某种意义复制成很多份，每份有一个层数的概念 在同一个图内遍历有一个法则，在不同层图之间遍历又有另外的法则 最后得到答案

对于这道题，p这一维即是分层图的层数 这里可以很明显地感知到，分层图与DP结合紧密

traid居然还有三和弦的意思！ilil

当你写不出来的时候，记住，还有一种方法叫做重构

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e3+5,INF=2147483647; int n,p,k; int tot,first[N],nxt[N*20],aim[N*20],wei[N*20]; int dis[N][21]; int vis[N][21]; struct traid{ int first,second,third; traid(){} traid(int a,int b,int c){first=a;second=b;third=c;} friend inline bool operator < (const traid &u,const traid &v){ return u.first<v.first; } }; priority_queue<traid>q; void ljb(int u,int v,int w){ ++tot; nxt[tot]=first[u]; first[u]=tot; aim[tot]=v; wei[tot]=w; return; } void Dijkstra(){ dis[1][0]=0; q.push(traid(0,1,0)); while(!q.empty()){ int u=q.top().second,p=q.top().third; q.pop(); if(vis[u][p]) continue; vis[u][p]=true; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(dis[v][p]>max(dis[u][p],wei[e])){ dis[v][p]=max(dis[u][p],wei[e]); q.push(traid(-dis[v][p],v,p)); } if(p<k&&dis[v][p+1]>dis[u][p]){ dis[v][p+1]=dis[u][p]; q.push(traid(dis[v][p+1],v,p+1)); } } } return; } int main(){ n=in,p=in,k=in; for(int i=1;i<=p;++i){ int u=in,v=in,w=in; ljb(u,v,w); ljb(v,u,w); } for(int i=1;i<=n;++i) for(int j=0;j<=k;++j) dis[i][j]=INF; Dijkstra(); if(dis[n][k]!=INF) printf("%d\n",dis[n][k]); else puts("-1"); return 0; }

相似例题

[JLOI2011]飞行路线

找到一条路径，前$k$大的边不计算，最小化剩下的边权和

二分的做法我YY不出来qwq

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=5e4+5,INF=2147483647; int n,m,k,s,t; int tot,first[N],nxt[N<<1],aim[N<<1],wei[N<<1]; int dis[N][20]; bool vis[N][20]; struct traid{ int first,second,third; traid(){}; traid(int a,int b,int c){first=a,second=b,third=c;} friend inline bool operator < (const traid &u,const traid &v){ return u.first<v.first; } }; priority_queue<traid>q; void ljb(int u,int v,int w){ ++tot; nxt[tot]=first[u]; first[u]=tot; aim[tot]=v; wei[tot]=w; return; } void Dijkstra(){ dis[s][0]=0; q.push(traid(0,s,0)); while(!q.empty()){ int u=q.top().second,p=q.top().third; q.pop(); if(vis[u][p]) continue; vis[u][p]=true; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(dis[v][p]>dis[u][p]+wei[e]){ dis[v][p]=dis[u][p]+wei[e]; q.push(traid(-dis[v][p],v,p)); } if(p<k&&dis[v][p+1]>dis[u][p]){ dis[v][p+1]=dis[u][p]; q.push(traid(-dis[v][p+1],v,p+1)); } } } return; } int main(){ n=in,m=in,k=in,s=in+1,t=in+1; for(int i=1;i<=m;++i){ int u=in+1,v=in+1,w=in; ljb(u,v,w); ljb(v,u,w); } for(int i=1;i<=n;++i) for(int j=0;j<=k;++j) dis[i][j]=INF; Dijkstra(); int res=INF; for(int i=0;i<=k;++i) res=min(res,dis[t][k]); if(res==1) res=0; if(res==INF) puts("-1"); else printf("%d\n",res); return 0; }

if(res==1) res=0;作弊嘿嘿嘿