分层图dp & 拆点连边

· 算法

继续看图论小寄巧的日报，发现之前的分层图咕了，那甚至是4.17昆明之前的事了

决意好好地补一补，然后发现没有什么东西可弄的..

高中的时候还以为是什么高深的东西..

就是说，如果一个点，或者一张图，有K种状态，那么我们可以建K层图，然后连边，记录转移的信息，来维护..

通信线路

给定 nn 个点， mm 条边的图，定义一条路径的花费为最大的边权

至多可以选择 kk 条边为0，问点 1→n1 \to n 最小的花费

于是我们可以开 k+1k+1 层图，然后对于所有边 (u,v)(u,v)
，给一个第 ii 层的 uu 指向第 i+1i+1 层的 vv 边权为0的边，每层图之间正常连边

然后dijkstra的转移改成 dis[v]=min(dis[v],max(dis[u],u))\mathtt{dis[v]=min(dis[v], max(dis[u],u))}，逝分合理

当然为了省空间，其实可以只设一个dis[k][i]表示到点i用了k条边的花费，然后简单转移一下，因为不难知道点 uu 只能把当前指向的点和上一层的同样点作为选项，所以不需要把图建出来

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
#define il inline
#define rg register
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef double db;
const int INF = 0x7fffffff;
const int inf = 0x3f3f3f3f;
const int MOD = 998244353;
const int mod = 1e9 + 7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
const int N = 1010;
int n, m, k;
int dis[N][N];
bool vis[N][N];
vector<pair<int, int>> adj[N];
priority_queue<pair<int, pair<int, int>>> q;
int main() {
 ios::sync_with_stdio(false);
 cin.tie(0);
 cin >> n >> m >> k;
 rep(i, 1, n) rep(j, 0, k) dis[i][j] = INF;
 for (int i = 1; i <= m; i++) {
   int u, v, w;
   cin >> u >> v >> w;
   adj[u].pb(mp(v, w));
   adj[v].pb(mp(u, w));
 }
 dis[1][0] = 0;
 q.push(mp(0, mp(1, 0)));
 while (!q.empty()) {
   int i = q.top().se.fi, j = q.top().se.se;
   q.pop();
   if (vis[i][j] == true)
     continue;
   vis[i][j] = true;
   for (int G = 0; G < adj[i].size(); G++) {
     int v = adj[i][G].fi, w = adj[i][G].se;
     if (dis[v][j] > max(dis[i][j], w)) {
       dis[v][j] = max(dis[i][j], w);
       q.push(mp(-dis[v][j], mp(v, j)));
     }
     if (j < k && dis[v][j + 1] > dis[i][j]) {
       dis[v][j + 1] = dis[i][j];
       q.push(mp(-dis[v][j + 1], mp(v, j + 1)));
     }
   }
 }
 int ans = INT_MAX;
 rep(i, 0, k) ans = min(ans, dis[n][i]);
 if (ans == INT_MAX)
   puts("-1");
 else
   cout << ans << endl;
 return 0;
}

[JLOI2011] 飞行路线

求的最小的最大边权改为最短路，做法也是一样

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  int s, t;
  cin >> s >> t;
	int tot = k * n + n - 1;
  vector<vector<pair<int, int>>> adj(k * n + n);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
    for (int j = 1; j <= k; ++j) {
			adj[u + j * n - n].push_back({v + j * n, 0});
			adj[v + j * n - n].push_back({u + j * n, 0});
			adj[u + j * n].push_back({v + j * n, w});
			adj[v + j * n].push_back({u + j * n, w});
    }
  }
	vector<int> dis(tot + 1, INT_MAX);
	dis[s] = 0;
	set<pair<int, int>> p;
	for (int i = 0; i <= tot; ++i)
		p.insert({dis[i], i});
	for (int i = 0; i <= tot; ++i) {
		int u = p.begin()->second;
		p.erase(p.begin());
		for (auto it : adj[u]) {
			int v = it.first, w = it.second;
			if (dis[v] > dis[u] + w) {
				p.erase({dis[v], v});
				dis[v] = dis[u] + w;
				p.insert({dis[v], v});
			}
		}
	}
	int Min = INT_MAX;
	for (int i = t; i <= tot; i += n) {
		Min = min(Min, dis[i]);
	}
	cout << Min << '\n';
  return 0;
}

咳咳我就是来水博客的

主要是今天看了那个Legacy的线段树节点连边，突然觉得这个东西好弱智，之前还是那种理解了写不出来的状态。。

还是太菜了

三倍经验

[BJWC2012]冻结

[USACO09FEB]Revamping Trails G