西安营销型网站建设,百度秒收录神器,合肥网络公司排行榜,pluto wordpressproblem
有两个国家#xff0c;国家 AAA 有 nnn 座城市#xff0c;国家 BBB 有 mmm 座城市#xff0c;两个国家间有若干条单向航线。
具体地#xff0c;有长度为 nnn 的数组 aaa 和长度为 mmm 的数组 bbb。国家 AAA 的第 iii 座城市有单向航线可以到达国家 BBB 的 1∼ai1…problem
有两个国家国家 AAA 有 nnn 座城市国家 BBB 有 mmm 座城市两个国家间有若干条单向航线。
具体地有长度为 nnn 的数组 aaa 和长度为 mmm 的数组 bbb。国家 AAA 的第 iii 座城市有单向航线可以到达国家 BBB 的 1∼ai1\sim a_i1∼ai 号城市。国家 BBB 的第 iii 座城市有单向航线可以到达国家 AAA 的 1∼bi1\sim b_i1∼bi 号城市。
定义一次膜拜为共 nmnmnm 座城市任选一座出发沿着单向航线走不重复经过城市最后回答出发城市的过程即一个简单有向环。
要求若干次膜拜加在一起经过 AAA 国家的城市 iii 不超过 cic_ici 次经过 BBB 国家城市 iii 不超过 did_idi 次。
在一次膜拜中起终点相同但仍然认为起点只经过了一次。
最大化膜拜次数并输出。
solution
这个单向航线很特别能到达对面的城市一定是从 111 开始编号的连续一段。
有个结论每次膜拜的路线一定是个二元环。 二元环可以用 dinic\text{dinic}dinic 网络流 O(n2n)O(n^2\sqrt n)O(n2n) / 匈牙利最大匹配 O(n3)O(n^3)O(n3) 跑。
左部点为 AAA 国城市右部点为 BBB 国城市。
当满足 ai≥j∧bj≥ia_i\ge j\wedge b_j\ge iai≥j∧bj≥i 时左部 iii 点和右部 jjj 点连一条边。
因为无法通过此题我们考虑能否模拟这个最大流的过程。
将 AAA 国城市限制当作 (i,ai)(i,a_i)(i,ai)BBB 国城市限制当作 (bi,i)(b_i,i)(bi,i)投放到二维平面上。 发现在二维平面图上对于 AAA 国城市 iii与其有单向航线的城市都在其下方。对于 BBB 国城市 jjj与其有单向航线的城市都在其左侧。
所以AAA 国城市 iii 只能和其右下方的 BBB 城市点进行匹配才能形成二元环。
将 AAA 国城市按 aia_iai 分类然后枚举 yayaya 常直线像扫描线一般上移顺便加入新的 BBB 国城市点。
贪心地城市 iii 会和离自己最近的 BBB 国城市匹配这个距离单指 xxx 轴上的距离。
大概就是更远的有更多适配情况先将要求较严苛的匹配了来。
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;
}
