洛谷P1948/USACO08JAN 电话线Telephone Lines

@Pelom  October 31, 2019

题意

无向图中,可选择$k$条边将边权变为$0$,求最小瓶颈最短路

数据范围:$1 \le n,k \le 1000,1 \le m \le 10000$

题解

分层图
每层内建原图,在层之间建边权为$0$的单向边,意为一次变化,因此共$k+1$层
为统计答案,由每一层的终点向超级汇点连一条权值为$0$的单向边

代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define mp make_pair
typedef pair<int,int> pi;
const int N=1000+10;
const int M=10000+10;
const int INF=0x3f3f3f3f;
int n,m,k,u,v,w;
int cnt;
int head[N*M],dis[N*M];
struct edge{
    int nxt,to,w;
} e[(M*4+N)*N];
inline void add(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
inline void Dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pi,vector<pi>,greater<pi> > Q;
    Q.push(mp(0,1));
    dis[1]=0;
    for(;!Q.empty();){
        pi p=Q.top();
        int u=p.second,d=p.first;
        Q.pop();
        if(d!=dis[u])
            continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>max(dis[u],e[i].w)){
                dis[v]=max(dis[u],e[i].w);
                Q.push(mp(dis[v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        for(int j=1;j<=k;j++){
            add(u+n*j,v+n*j,w);
            add(v+n*j,u+n*j,w);
            add(u+n*(j-1),v+n*j,0);
            add(v+n*(j-1),u+n*j,0);
        }
    }
    for(int i=0;i<=k;i++)
        add(n+n*i,n*(k+1)+1,0);
    Dijkstra();
    printf("%d",dis[n*(k+1)+1]==INF?-1:dis[n*(k+1)+1]);
    return 0;
}

添加新评论