膜拜大丹（结论+二元环）

膜拜大丹（结论+二元环） problem

有两个国家，国家 A A A 有 n n n 座城市，国家 B B B 有 m m m 座城市，两个国家间有若干条单向航线。

具体地，有长度为 n n n 的数组 a a a 和长度为 m m m 的数组 b b b。国家 A A A 的第 i i i 座城市有单向航线可以到达国家 B B B 的 1 ∼ a i 1sim a_i 1∼ai​ 号城市。国家 B B B 的第 i i i 座城市有单向航线可以到达国家 A A A 的 1 ∼ b i 1sim b_i 1∼bi​ 号城市。

定义一次膜拜为：共 n + m n+m n+m 座城市，任选一座出发，沿着单向航线走，不重复经过城市，最后回答出发城市的过程，即一个简单有向环。

要求若干次膜拜加在一起，经过 A A A 国家的城市 i i i 不超过 c i c_i ci​ 次，经过 B B B 国家城市 i i i 不超过 d i d_i di​ 次。

在一次膜拜中起终点相同，但仍然认为起点只经过了一次。

最大化膜拜次数并输出。

solution

这个单向航线很特别，能到达对面的城市一定是从 1 1 1 开始编号的连续一段。

有个结论：每次膜拜的路线一定是个二元环。

二元环可以用 dinic text{dinic} dinic 网络流 O ( n 2 n ) O(n^2sqrt n) O(n2n ​) / 匈牙利最大匹配 O ( n 3 ) O(n^3) O(n3) 跑。

左部点为 A A A 国城市，右部点为 B B B 国城市。

当满足 a i ≥ j ∧ b j ≥ i a_ige jwedge b_jge i ai​≥j∧bj​≥i 时，左部 i i i 点和右部 j j j 点连一条边。

因为无法通过此题，我们考虑能否模拟这个最大流的过程。

将 A A A 国城市限制当作 ( i , a i ) (i,a_i) (i,ai​)， B B B 国城市限制当作 ( b i , i ) (b_i,i) (bi​,i)，投放到二维平面上。

发现，在二维平面图上，对于 A A A 国城市 i i i，与其有单向航线的城市都在其下方。对于 B B B 国城市 j j j，与其有单向航线的城市都在其左侧。

所以， A A A 国城市 i i i 只能和其右下方的 B B B 城市点进行匹配，才能形成二元环。

将 A A A 国城市按 a i a_i ai​ 分类，然后枚举 y = a y=a y=a 常直线，像扫描线一般上移，顺便加入新的 B B B 国城市点。

贪心地，城市 i i i 会和离自己最近的 B B B 国城市匹配（这个距离单指 x x x 轴上的距离）。

大概就是更远的有更多适配情况，先将要求较严苛的匹配了来。

code

#include 
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( "%lldn", ans );
    return 0;
}