P5331 SNOI2019 通訊

2022-09-22 20:18:20 字數 1509 閱讀 6173

p5331 snoi2019通訊

我省去年省選題。

拿到的時候直接想了個80分做法(震驚,暴力80分,不過去年好像進隊要325分,,,)。

然後同機房聚銠教了滿分做法,以為自己理解了,發現理解錯了。

80分暴力連邊方式:

\(s \rightarrow i_1\) 費用0, 流量1

\(i_1 \rightarrow t\) 費用w, 流量1

\(i_2 \rightarrow t\) 費用0, 流量1

然後 \(i_1\) 向前面所有的 \(j_2\) 連邊,費用 \(\mid a_i - a_j \mid\) 流量1

利用cdq分治優化建圖(主席樹啥的隨便寫,我懶)

簡單來說就是保證下標大的只能連下標小的,那麼考慮區間 \([l, r]\)(下標區間) 其中 \([mid+1, r]\) 的一段必定可以向 \([l, mid]\) 的一段連邊。那麼我們將這段區間有的權值建立一條虛鏈,然後跑網路瘤就行。注意去重,離散化就行。

void lk(ll l, ll r) 

for (ll i = l; i <= r; i++)

tot += num;

}

#include #include #include #include #include typedef long long ll;

const ll maxn = 8e5+10;

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct edge e[maxn];

ll n, w, x[maxn], s, t, head[maxn], cnt = -1, b[maxn], tot = 0, p[maxn][2], dis[maxn], vis[maxn], ans;

void add(ll, ll, ll, ll);

void adde(ll, ll, ll, ll);

ll dfs(ll, ll);

void lk(ll, ll);

bool spfa();

int main()

for (ll i = 1; i <= n; i++)

lk(1, n);

while (spfa())

printf("%lld\n", ans);

return 0;

}bool spfa() }}

}return dis[n] != inf;

}ll dfs(ll n, ll flow)

}if (!used) dis[n] = 0;

return used;

}void lk(ll l, ll r)

for (ll i = l; i <= r; i++)

tot += num;

}void add(ll x, ll y, ll v, ll f)

void adde(ll x, ll y, ll v, ll f)

洛谷P5331 SNOI2019 通訊

洛谷 題意 n 個哨站排成一列,第 i 個哨站的頻段為 a i 。 現在每個哨站可以選擇 問最終最小代價和為多少。 思路 但直接來搞的話邊的...

SNOI2019 字串

題目 看起來非常一眼啊,我們完全可以 std sort 來解決這歌問題 於是現在的問題轉化成了比較函式怎麼寫 隨便畫一下就會發現前面的好幾位...

SNOI2019 通訊

傳送門 我們可以不難想到這樣一種費用流做法 每個點拆成兩個點,對於其中一類點 u ,我們直接連邊 s overset u overset t 表示這個點直接連到控制中心。 對於兩個哨站 i j j i 的連邊,我們就連邊 s overset i overset j prime overset t 。...