POJ-3662 Telephone Lines(分层图最短路|二分)

解法参考进阶指南

题意：算1到N的路径上把K条边的边权变为0后路径中边权的最大值最小。(无向图中找一条1到N的路径，使得K+1大的边权尽量小。)

解法1：分层图最短路。SPFA维护DP。

设\(f[i][j]\)表示从1号点到\(i\)号点路径上把\(j\)条边变为0后最大边权的最小值。

对于一条边而言，要么把他变为0，要么不变为0。

变为0：\(f[v][j+1] = min(f[v][j+1], f[u][j+1])\)

不变： \(f[v][j] = min(f[v][j], max(f[u][j], w(u,v)))\)

转移过程如果直接枚举\(j\)复杂度太高，因此使用SPFA维护这个DP。

最终的答案就是所有\(f[n][x](x<=k)\)的最小值

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n, p, k, ans;

const int maxn = 1e4+10, N = 1e3+10;
struct E{int to, next, w;}e[maxn<<1];
int head[maxn], cnt;
void init() {
  memset(head,-1,sizeof head);
  cnt = 0;
}
void add(int u, int v, int w) {
  e[++cnt].to = v, e[cnt].w = w, e[cnt].next = head[u], head[u] = cnt;
}

struct node{
  node(){}
  node(int ID, int P) {
    id = ID, p = P;
  }
  int id, p;
};
int f[N][maxn]; //1号点到第i个点使用了j次免费路径上的最大边权
bool inq[N][maxn];
const int inf = 0x3f3f3f3f;
void spfa(int s) {
  memset(f,0x3f,sizeof f);
  f[s][0] = 0;
  queue q;
  q.push(node(s,0));
  inq[s][0] = 1;
  while (!q.empty()) {
    int u = q.front().id, pp = q.front().p; q.pop();
    inq[u][pp] = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if (max(f[u][pp],w) < f[v][pp]) {
        f[v][pp] = max(f[u][pp],w);
        if (!inq[v][pp]) q.push(node(v,pp)), inq[v][pp] = 1;
      }
      if (pp+1<=k && f[u][pp] < f[v][pp+1]) {
        f[v][pp+1] = f[u][pp];
        if (!inq[v][pp+1]) q.push(node(v,pp+1)), inq[v][pp+1] = 1;
      }
    }
  }
}

int main() {
  init();
  scanf("%d%d%d",&n,&p,&k);
  for (int i = 1; i <= p; i++) {
    int u, v, w;
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w);
    add(v,u,w);
  }
  ans = inf;
  spfa(1);
  int ans = inf;
  for (int i = 0; i <= k; i++) ans = min(ans, f[n][i]);
  printf("%d\n",ans==inf? -1 : ans);
  return 0;
}

解法2：二分答案check最短路。

该解法应该更容易想到。每次二分重新构建一张图，对于每次二分出的一个值\(x\)，把边权\(<=x\)的边加入图中，并把边权设为0，把边权\(>x\)的边加入图中，并把边权设为1，这样从1到N跑一遍最短路，代表把最短路的值的那么多条边变成0之后1到N的路径上所有的值都\(<=x\)了，然后再check最短路和k哪个大即可。

这里代码用dijkstra跑最短路(不会01BFS)，速度还是挺快的。

#pragma GCC optimize(2)
#include 
#include 
#include 
#include 
#include 
#include 
#define pb push_back
#define mp make_pair
using namespace std;

int n, p, k;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int dis[maxn];
bool vis[maxn];

vector, int> > vec;
vector > e[maxn];

struct cmp{
  bool operator()(const pair &x, const pair &y) {
    return x.second > y.second;
  }
};

int dj(int s) {
  memset(vis,0,sizeof vis);
  memset(dis,0x3f,sizeof dis);
  priority_queue, vector > , cmp> q;
  q.push(mp(s,0));
  dis[s] = 0;
  while (!q.empty()) {
    int u = q.top().first, ww = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = 0; i < e[u].size(); i++) {
      int v = e[u][i].first, w = e[u][i].second;
      if (vis[v]) continue;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push(mp(v,dis[v]));
      }
    }
  }
  return dis[n];
} 

bool check(int x) {
  for (int i = 1; i <= n; i++) e[i].clear();
  for (int i = 0; i < vec.size(); i++) {
    if (vec[i].second <= x) {
      e[vec[i].first.first].pb(mp(vec[i].first.second,0));
      e[vec[i].first.second].pb(mp(vec[i].first.first,0));
    } else {
      e[vec[i].first.first].pb(mp(vec[i].first.second,1));
      e[vec[i].first.second].pb(mp(vec[i].first.first,1));
    }
  }
  return dj(1) <= k;
}

int main() {
  scanf("%d%d%d",&n,&p,&k);
  for (int i = 1; i <= p; i++) {
    int u, v, w;
    scanf("%d%d%d",&u,&v,&w);
    vec.pb(mp(mp(u,v),w));
  }
  int l = 0, r = inf;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }
  printf("%d\n",l==inf ? -1 : l);
  return 0;
}