problem

有兩個國家，國家 $A$ 有 $n$ 座城市，國家 $B$ 有 $m$ 座城市，兩個國家間有若干條單向航線。

具體地，有長度為 $n$ 的數組 $a$ 和長度為 $m$ 的數組 $b$。國家 $A$ 的第 $i$ 座城市有單向航線可以到達國家 $B$ 的 $1～a_i$ 號城市。國家 $B$ 的第 $i$ 座城市有單向航線可以到達國家 $A$ 的 $1～b_i$ 號城市。

定義一次膜拜為：共 $n+m$ 座城市，任選一座出發，沿著單向航線走，不重復經過城市，最后回答出發城市的過程，即一個簡單有向環。

要求若干次膜拜加在一起，經過 $A$ 國家的城市 $i$ 不超過 $c_i$ 次，經過 $B$ 國家城市 $i$ 不超過 $d_i$ 次。

在一次膜拜中起終點相同，但仍然認為起點只經過了一次。

最大化膜拜次數并輸出。

solution

這個單向航線很特別，能到達對面的城市一定是從 $1$ 開始編號的連續一段。

有個結論：每次膜拜的路線一定是個二元環。

二元環可以用 $\text{dinic}$ 網絡流 $O(n^2\sqrt{n})$ / 匈牙利最大匹配 $O(n^3)$ 跑。

左部點為 $A$ 國城市，右部點為 $B$ 國城市。

當滿足 $a_i\ge j\wedge b_j\ge i$ 時，左部 $i$ 點和右部 $j$ 點連一條邊。

因為無法通過此題，我們考慮能否模擬這個最大流的過程。

將 $A$ 國城市限制當作 $(i,a_i)$，$B$ 國城市限制當作 $(b_i,i)$，投放到二維平面上。

發現，在二維平面圖上，對于 $A$ 國城市 $i$，與其有單向航線的城市都在其下方。對于 $B$ 國城市 $j$，與其有單向航線的城市都在其左側。

所以，$A$ 國城市 $i$ 只能和其右下方的 $B$ 城市點進行匹配，才能形成二元環。

將 $A$ 國城市按 $a_i$ 分類，然后枚舉 $y=a$ 常直線，像掃描線一般上移，順便加入新的 $B$ 國城市點。

貪心地，城市 $i$ 會和離自己最近的 $B$ 國城市匹配（這個距離單指 $x$ 軸上的距離）。

大概就是更遠的有更多適配情況，先將要求較嚴苛的匹配了來。

code

#include <bits/stdc++.h> using namespace std; #define maxn 500005 int n, m; int a[maxn], b[maxn], c[maxn], d[maxn]; multiset < pair < int, int > > s; vector < int > g[maxn];int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%d", &a[i] );for( int i = 1;i <= m;i ++ ) scanf( "%d", &b[i] );for( int i = 1;i <= n;i ++ ) scanf( "%d", &c[i] );for( int i = 1;i <= m;i ++ ) scanf( "%d", &d[i] );for( int i = 1;i <= n;i ++ ) g[a[i]].push_back( i );long long ans = 0;for( int i = 1;i <= m;i ++ ) {s.insert( make_pair( b[i], d[i] ) );for( int k : g[i] ) {while( ! s.empty() ) {auto it = s.lower_bound( make_pair( k, 0 ) );if( it == s.end() ) break;pair < int, int > t = *it;s.erase( it );if( t.second > c[k] ) {t.second -= c[k];ans += c[k];c[k] = 0;s.insert( t );break;}else c[k] -= t.second, ans += t.second;}}}printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的膜拜大丹（结论+二元环）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。