天天看點
傳回

通信線路（最短路+二分、二維最短路、分層圖最短路）

通信線路

    • 題意
    • 做法1：二分
      • 代碼1（Dijkstra）
      • 代碼2（spfa）
    • 做法2：二維最短路
      • 代碼
    • 做法3：分層圖最短路
      • 代碼

題意

給定一個無向圖，可以選擇一條線路，将其 k k k條邊邊權變為 0 0 0，使得剩下邊的邊權最大值最小。求這個最小值。

做法1：二分

一看最大值最小，首先考慮二分，二分答案。二分過程中，如果大于 m i d mid mid的邊數大于 k k k，那麼這個最小值一定大于目前二分到的答案。

代碼1（Dijkstra） 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 20010, inf = 0x3f3f3f3f;

typedef pair<int,int> pii;

int n,m,k;
int h[N], e[M], ne[M], w[M], idx;
int dist[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 ++;
}

bool check(int limit)
{
    memset(dist,0x3f,sizeof(dist));
    memset(st,false,sizeof(st));
    dist[1] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    heap.push({0,1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];~i;i=ne[i]){
            int j = e[i];
            int x = w[i] > limit;
            if(dist[j]>distance+x){
                dist[j] = distance + x;
                heap.push({dist[j],j});
            }
        }
    }
    return dist[n] <= k;
}

int main()
{
    cin >> n >> m >> k;
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c), add(b,a,c);
    }
    int l = 0, r = 1e6 + 1;
    while(l<r){
        int mid =  l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(r==1e6+1) cout << -1 << endl;
    else cout << r << endl;
    return 0;
}

代碼2（spfa） 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 20010, inf = 0x3f3f3f3f;

int n,m,k;
int h[N], e[M], ne[M], w[M], idx;
int dist[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 ++;
}

bool check(int limit)
{
    memset(dist,0x3f,sizeof(dist));
    memset(st,false,sizeof(st));
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    st[1] = true;
    while(que.size()){
        int t = que.front();
        que.pop();
        st[t] = false;
        for(int i=h[t];~i;i=ne[i]){
            int j = e[i];
            int distance = w[i] > limit;
            if(dist[j]>dist[t]+distance){
                dist[j] = dist[t] + distance;
                if(!st[j]){
                    st[j] = true;
                    que.push(j);
                }
            }
        }
    }
    return dist[n] <= k;
}

int main()
{
    cin >> n >> m >> k;
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c), add(b,a,c);
    }
    int l = 0, r = 1e6 + 1;
    while(l<r){
        int mid =  l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(r==1e6+1) cout << -1 << endl;
    else cout << r << endl;
    return 0;
}

做法2：二維最短路

定義 D ( x , k ) D(x,k) D(x,k)為到 x x x這個點總共免費更新 k k k條邊的最短路徑。我們考慮從 x x x到 y y y這條邊，假設邊權為 w [ i ] w[i] w[i]。如果這條邊免費更新的話，那麼可以用 D ( x , k ) D(x,k) D(x,k)來更新 D ( y , k + 1 ) D(y,k+1) D(y,k+1)；如果這條邊不免費更新的話，那麼可以用 m a x ( D ( x , k ) , w [ i ] ) max(D(x,k),w[i]) max(D(x,k),w[i])來更新 D ( y , k ) D(y,k) D(y,k)。這裡注意一點，就是在轉移的過程中，有 k < K k < K k<K的限制條件。另外，如果路徑邊數小于 K K K，那麼往後的都沒有更新，是以需要找一個最小值。

代碼 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 20010, inf = 0x3f3f3f3f;

typedef pair<int,int> pii;
typedef pair<int,pii> pip;

int n, m, K;
int h[N], e[M], ne[M], w[M], idx;
int dist[N][N];
bool st[N][N];

void add(int a,int b,int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1][0] = 0;
    priority_queue<pip,vector<pip>,greater<pip>> heap;
    heap.push({0,{1,0}});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second.first, k = t.second.second;
        if(st[ver][k]) continue;
        st[ver][k] = true;
        for(int i=h[ver];~i;i=ne[i]){
            int j = e[i];
            if(k < K){
                if(dist[j][k+1] > dist[ver][k]){
                    dist[j][k+1] = dist[ver][k];
                    heap.push({dist[j][k+1],{j,k+1}});
                }
            }
            if(dist[j][k] > max(dist[ver][k],w[i])){
                dist[j][k] = max(dist[ver][k],w[i]);
                heap.push({dist[j][k],{j,k}});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&K);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c), add(b,a,c);
    }
    dijkstra();
    int tmp = inf;
    for(int i=0;i<=K;i++) tmp = min(tmp, dist[n][i]);
    if(tmp==inf) printf("-1\n");
    else printf("%d\n",tmp);
    return 0;
}

做法3：分層圖最短路

建立 K + 1 K+1 K+1層，對于一條邊，起點為 u u u，終點為 v v v，邊權為 w w w。同層之間，連一條長度為 w w w的邊，上一層向下一層連一條長度為 0 0 0的邊。對于同一個點，上一層向下一層連一條長度為 0 0 0的邊。

代碼 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;

const int N = 1000010, M = 4e7 + 10;
const ll inf = 1e18;

int n, m, K;
int h[N], e[M], ne[M], idx;
ll w[M];
ll dist[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 dijkstra()
{
    for(int i=1;i<=N;i++) dist[i] = inf;
    memset(st,false,sizeof(st));
    dist[1] = 0;
    priority_queue<pli,vector<pli>,greater<pli>> heap;
    heap.push({0,1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];~i;i=ne[i]){
            int j = e[i];
            if(dist[j]>max(dist[ver],w[i])){
                dist[j] = max(dist[ver],w[i]);
                heap.push({dist[j],j});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&K);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b;
        ll c;
        scanf("%d%d%lld",&a,&b,&c);
        add(a,b,c), add(b,a,c);
        for(int j=1;j<=K;j++){
            add(a+(j-1)*n,b+j*n,0);
            add(b+(j-1)*n,a+j*n,0);
            add(a+j*n,b+j*n,c);
            add(b+j*n,a+j*n,c);
        }
    }
    for(int i=1;i<=n;i++){
        for(int k=0;k<K;k++){
            add(k*n+i,(k+1)*n+i,0);
        }
    }
    dijkstra();
    if(dist[(K+1)*n]==inf) printf("-1\n");
    else printf("%lld\n",dist[(K+1)*n]);
    return 0;
}
# 最短路 圖論
上一篇: 最短時間過橋
下一篇: Elevators UVALive - 7015 （水最短路）

繼續閱讀