problem

luogu-P4542

solution

剛開始就直觀感覺 $dp$ 不動，卻有個看似“理所當然”的貪心：每次跑 $k$ 個人所在點到擴展據(jù)點的最短距離，然后讓最近的人去破環(huán)那個據(jù)點。

啪啪敲完后小樣例（實在太水）就過了，然后大樣例就$\dots$爆炸了。

再然后就可以隨便手玩很小的情況都可以 $\text{hack}$ 掉這個貪心。

fine貪心也不行

當你發(fā)現(xiàn)貪心貪不動，$dpp$ 不動，你再看數(shù)據(jù)范圍可以接受 $2/3$ 次方，$n,m$ 小的離譜卻又比狀壓大，你不妨再看看我們可愛的網(wǎng)絡流。

我一直把網(wǎng)絡流當成智能化的貪心。

---

好，現(xiàn)在我們已經(jīng)知道 猜想 到是網(wǎng)絡流了，接下來就是建圖的問題了。

首先要求出任意兩個據(jù)點之間的最短距離，$\text{floyd}$ 都可以接受。

但是這里有個限制：顯然這個最短路上中間經(jīng)過的據(jù)點編號不能大于起終點的編號。

在 $\text{floyd}$ 的放縮更新中加上判斷即可。

然后網(wǎng)絡流上的圖肯定是編號小的到編號大的點連邊。

每個點都可能成為人最后停留的位置，所以每個點都要向匯點連邊。

源點一開始只給初始點輸送 $k$ 的流量，網(wǎng)絡最后流出的 $k$ 條路徑就是這 $k$ 個人的行動方案。

但這里我們要保證每個點被走的次數(shù) $\ge 1$。

可以選擇直接上下界網(wǎng)絡流，也可以將網(wǎng)絡流轉(zhuǎn)化成費用流。

對每個點拆成入點和出點，連兩條邊，一條特殊的費用為 $?\infty$，流量為 $1$，另一條是普通的無費用，流量無限制。

這樣子為了使得費用最小化，網(wǎng)絡流肯定會流過所有點的特殊邊。

這樣子就達到了每個點至少被走過一次的要求。

最后再把費用加回來就行了 $n?\infty$。

這個建圖的思路基礎(chǔ)為 $k$ 條可重鏈覆蓋圖上所有點。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3f3f3f3f #define maxn 400 #define maxm 300000 struct node { int to, nxt, flow, cost; }E[maxm]; int cnt = -1, n, m, K, s, t; int head[maxn], lst[maxn], dep[maxn], vis[maxn]; int dis[maxn][maxn]; queue < int > q;void addedge( int u, int v, int w, int c ) {E[++ cnt] = { v, head[u], w, c }, head[u] = cnt;E[++ cnt] = { u, head[v], 0,-c }, head[v] = cnt; }void build() {memset( head, -1, sizeof( head ) );s = 0, t = n << 1 | 1;addedge( s, 1, K, 0 );for( int i = 1;i <= n;i ++ ) {addedge( i, i + n, 1, -inf );addedge( i, i + n, inf, 0 );addedge( i + n, t, inf, 0 );for( int j = i + 1;j <= n;j ++ ) {if( dis[i][j] != inf )addedge( i + n, j, inf, dis[i][j] );}} }bool SPFA() {memset( dep, 0x3f, sizeof( dep ) );memset( lst, -1, sizeof( lst ) );dep[s] = 0, q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop(); vis[u] = 0;for( int i = head[u];~ i;i = E[i].nxt ) {int v = E[i].to;if( dep[v] > dep[u] + E[i].cost and E[i].flow ) {dep[v] = dep[u] + E[i].cost; lst[v] = i;if( ! vis[v] ) q.push( v ), vis[v] = 1;}}}return ~lst[t]; }int MCMF() {int ans = 0;while( SPFA() ) {int flow = inf;for( int i = lst[t];~ i;i = lst[E[i ^ 1].to] )flow = min( flow, E[i].flow );for( int i = lst[t];~ i;i = lst[E[i ^ 1].to] ) {E[i ^ 1].flow += flow;E[i].flow -= flow;ans += flow * E[i].cost;}}return ans + inf * n; }signed main() {scanf( "%lld %lld %lld", &n, &m, &K );n ++;for( int i = 1;i <= n;i ++ )for( int j = 1;j <= n;j ++ )dis[i][j] = inf;for( int i = 1, u, v, w;i <= m;i ++ ) {scanf( "%lld %lld %lld", &u, &v, &w );u ++, v ++;dis[u][v] = dis[v][u] = min( w, dis[u][v] );}for( int k = 1;k <= n;k ++ )for( int i = 1;i <= n;i ++ )for( int j = 1;j <= n;j ++ )if( k < max( i, j ) )dis[i][j] = min( dis[i][j], dis[i][k] + dis[k][j] );build();printf( "%lld\n", MCMF() );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[ZJOI2011]营救皮卡丘（费用流 + 最短路）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。