problem

luogu-P3344

solution

這個題面，這個數(shù)據(jù)范圍，完完全全就是網(wǎng)絡(luò)流宗教。。然而我發(fā)現(xiàn)建不出來。

很多一眼網(wǎng)絡(luò)流最后卻不是網(wǎng)絡(luò)流而往往是 $dp$ 的題目都有一個特性：一個點可以流出多條流量，流入流量卻只能為 $1$。

我曾嘗試過對點加兩條邊，一條流量為 $1$ 帶花費(fèi)，另一條流量無窮不帶花費(fèi)，然后強(qiáng)制先流特殊邊，這就必須要用費(fèi)用流來做到。

但題目所求往往相反，也就是我強(qiáng)制先流要用負(fù)花費(fèi)，求出的是最大費(fèi)用，而題目卻要最小費(fèi)用。

---

首先我們把所有不能被任何一個網(wǎng)絡(luò)架點覆蓋的景點刪去，就解決了第一小問。

問題轉(zhuǎn)化成了將所有點全覆蓋的最小花費(fèi)。

此題需要尋找一個結(jié)論：景點按 $x$ 排序后，每個網(wǎng)絡(luò)架點覆蓋的點一定是景點的一段連續(xù)區(qū)間。

由 所有網(wǎng)絡(luò)架的圓心都在矩形外 以及 所有網(wǎng)絡(luò)架的半徑均相同 這兩個性質(zhì)確保該結(jié)論的正確性。

注意這個結(jié)論是 所有圓心均在矩形上方 / 所有圓心均在矩形下方 分類后才成立。

于是我們就設(shè) $f(i,j,k):$ 考慮前 $i$ 個景點，最后一次使用圓心在矩陣上方的網(wǎng)絡(luò)架為 $j$，最后一次使用圓心在矩陣下方的網(wǎng)絡(luò)架為 $k$。

$i$ 景點能被圓心在矩陣上方的第 $j$ 個網(wǎng)絡(luò)架覆蓋，則再枚舉一下矩陣上方的網(wǎng)絡(luò)架上一次用的是哪個：

$f(i,j,k)=\min \{f(i?1,o,k)\}+c(j)$。

圓心在矩陣下方的轉(zhuǎn)移同理。

時間復(fù)雜度就是非常樸素的 $O(n^4)$。

注意：我們的 $f$ 狀態(tài)設(shè)計不再是常見到，使用前 $j/k$ 個圓心在矩陣上 / 下方的網(wǎng)絡(luò)架，而是直接最近一次使用的編號。

所以實際上這個網(wǎng)絡(luò)架的使用編號是反復(fù)變化跳躍的。

看似并不是一個圓會覆蓋一段連續(xù)點的方案。

但實際上這些不合法的方案一定不會成為最優(yōu)解，因為多次計算了網(wǎng)絡(luò)架點的搭建花費(fèi)。

而一個圓覆蓋一段連續(xù)點的最優(yōu)方案也統(tǒng)計進(jìn)了，所以最后答案是不會受到影響的。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 105 int n, m, R, cnt, cntd, cntu; int f[maxn][maxn][maxn]; struct NB { int x, y; }s[maxn], g[maxn]; struct DK { int x, y, c; }p[maxn], d[maxn], u[maxn];bool check( DK o, NB w ) { return (o.x - w.x) * (o.x - w.x) + (o.y - w.y) * (o.y - w.y) <= R * R; }signed main() {scanf( "%lld %lld %lld", &n, &m, &R );for( int i = 1;i <= n;i ++ ) scanf( "%lld %lld", &s[i].x, &s[i].y );for( int i = 1;i <= m;i ++ ) scanf( "%lld %lld %lld", &p[i].x, &p[i].y, &p[i].c );for( int i = 1;i <= n;i ++ ) {for( int j = 1;j <= m;j ++ )if( check( p[j], s[i] ) ) {g[++ cnt] = s[i];break;}}sort( g + 1, g + cnt + 1, []( NB a, NB b ) { return a.x < b.x; } );for( int i = 1;i <= m;i ++ )if( p[i].y < 0 ) d[++ cntd] = p[i];else u[++ cntu] = p[i];memset( f, 0x3f, sizeof( f ) );f[0][0][0] = 0;for( int i = 1;i <= cnt;i ++ )for( int j = 0;j <= cntu;j ++ )for( int k = 0;k <= cntd;k ++ ) {if( j and check( u[j], g[i] ) ) {f[i][j][k] = f[i - 1][j][k];for( int o = 0;o <= cntu;o ++ )f[i][j][k] = min( f[i][j][k], f[i - 1][o][k] + u[j].c );}if( k and check( d[k], g[i] ) ) {f[i][j][k] = f[i - 1][j][k];for( int o = 0;o <= cntd;o ++ )f[i][j][k] = min( f[i][j][k], f[i - 1][j][o] + d[k].c );}}int ans = 1e18;for( int i = 0;i <= cntu;i ++ )for( int j = 0;j <= cntd;j ++ )ans = min( ans, f[cnt][i][j] );printf( "%lld\n%lld\n", cnt, ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[ZJOI2015]幻想乡 Wi-Fi 搭建计划（dp + 结论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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