9.3/9.4
P3376 【模板】网络最大流
因为 Dinic 对于求最大流是比较优的算法，考虑对 Dinic 进行一个复习
Dinic 属于 Ford-Fulkerson 增广路算法，每次增广前我们都先用 BFS 将图分层，每个点的层数都是其距离源点的最短距离
求解思路如下：
-
对原图进行 BFS 构建分层图
-
考虑 EK 算法的核心问题在于一次只能扩展一条增广路，我们在 Dinic 中为了优化考虑使用 DFS 来一次寻找多条增广路
DFS 可以同时寻找出多条增广路，因此相对来说 Dinic 对于 EK 算法较优
此时我们就完成了 Dinic 算法的基础，乍一看单次 DFS 时间复杂度是 \(O(VE)\) 的，但是我们发现一个问题：DFS 可能会经过很多次同一个点，那么复杂度就是不严格的
考虑对 Dinic 进行优化
-
当前弧优化：
这个优化力度较大，而且直接作用于复杂度上，不会负优化，负优化就是打假了
由于我不知道怎么描述所以直接用 OI-wiki 上内容
如果某一时刻我们已经知道边 \((u, v)\) 已经增广到极限（边 \((u, v)\) 已无剩余容量或 \(v\) 的后侧已增广至阻塞），则 \(u\) 的流量没有必要再尝试流向出边 \((u, v)\)。
因此对于每个结点 \(u\)，我们直接维护 \(u\) 的出边表中第一条还有必要尝试的出边，下次就直接从这条边开始推，因为这个边之前的肯定已经推满了
我们称维护的这个指针为当前弧，那么这个优化就是当前弧优化
在使用当前弧优化的情况下单次 DFS 复杂度是严格的 \(O(VE)\)
-
证明
每次找增广路最多找 \(|E|\) 条，长度最多为 \(|V|\)，分层图层数严格递增，最多会建 \(|V|\) 次分层图
那么 Dinic 的复杂度就是 \(O(V^2E)\) 的
-
-
无用点优化
如果有流量流向一个点的时候，这个点流不动了，那么就说明它在当前分层图上不再能做出贡献，可暂时删去
点击查看代码
int Head[N],ver[N],Edge[N],nxt[N],d[N];
int now[N],tot,n,m,s,t,maxflow;
inline void Add(int x,int y,int z){
ver[++tot] = y;
Edge[tot] = z;
nxt[tot] = Head[x];
Head[x] = tot;
ver[++tot] = x;
Edge[tot] = 0;
nxt[tot] = Head[y];
Head[y] = tot;
}
queue<int> q;
inline bool BFS(){
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(s);
d[s] = 1; now[s] = Head[s];
while(q.size()){
int x = q.front(); q.pop();
for(int i=Head[x] ; i ; i=nxt[i]){
if(Edge[i] && !d[ver[i]]){
q.push(ver[i]);
now[ver[i]] = Head[ver[i]];
d[ver[i]] = d[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
}
inline int Dinic(int x,int f){
if(x==t) return f;
int rest = f;
for(int i = now[x];i && rest;i = nxt[i]){
now [x] = i;
if(Edge[i] && d[ver[i]] == d[x] + 1){
int k = Dinic(ver[i],min(rest,Edge[i]));
if(!k) d[ver[i]] = 0;
Edge[i] -= k;
Edge[i^1] += k;
rest -= k;
}
}
return f - rest;
}
inline void In(){
cin >> n >> m >> s >> t;
tot = 1;
for_(i,1,m){
int x,y,z;
cin >> x >> y >> z;
Add(x,y,z);
}
while(BFS())
maxflow += Dinic(s,inf);
cout << maxflow << endl;
}
9.5
P4722 【模板】最大流 加强版 / 预流推进
我们发现这道题和上一道题基本没有区别，主要的区别是本题数据范围开的更大了，\(O(V^2E)\) 的 Dinic 无法通过
经过测试，朴素 Dinic 在本题只有 \(16\) 分，考虑对 Dinic 进行优化（因为我不会预流推进）
对于 Dinic 有三种做法：Improved Dinic，LCT Dinic 和 Dinic 的玄学优化
个人采用的是 Dinic 的玄学优化
-
先不算反向边跑一边 Dinic，计算反向边的权值，然后加上权值之后再跑一边 Dinic
-
将所有边按照其容量二进制下的位数从大到小排序，位数相同的合并成一段。
顺序枚举每一段，在残量网络中加入这一段所有的边，跑一次Dinic，将新增广的流量加入答案
这样就可以通过本题
(模拟赛)
OI赛制怎么不给大样例啊
T1 dance
最开始想了个假结论然后被自己 \(hack\) 了，\(hack\) 数据010010001
乱搞了一个神秘做法不知道会不会被卡，考虑先记录每个男生/女生所处的位置，然后从大到小枚举区间，看区间内男生和女生人数是否相同，若相同则直接跳出，否则继续寻找
我们先判断男生和女生哪一个更多，然后在记录时记录其中较少的那个，最劣复杂度 \(O(tot^2)\)，\(tot\) 为男生和女生中较少的一个
然后特判一些情况，剩下的听天由命，然后果然有问题
int n,pos[N],tot,Sum;
bool a[N];
inline void In(){
cin >> n;
for_(i,1,n){
cin >> a[i];
if(a[i]) Sum+=1;
}
if(Sum==0 || Sum==n) {
cout << 0;
return;
}
if(Sum==n-Sum){
cout << n;
return;
}
if(Sum>n-Sum){
for_(i,1,n){
if(!a[i]) pos[++tot] = i;
}
}
else{
for_(i,1,n){
if(a[i]) pos[++tot] = i;
}
}
_for(i,tot,1){
for_(j,1,i-1){
int sum = pos[i]-pos[j]+1; // 区间内人数总和
int sum1 = i-j+1 ;// 区间男生/女生人数总和
int sum2 = sum - sum1;// 区间女生/男生人数总和
if(sum1==sum2){
cout << sum1 + sum2;
return;
}
}
}
cout << 2;
return;
}
考虑我们对这个求男生和女生人数的差值的前缀和，假设这个值是 \(t\)，然后我们只需要在两侧找到相同的 \(t\) 即可
然后直接求出区间的长度，在这些长度里求最大值即可
复杂度 \(O(n)\)
int n,a[N],q[N],m=1000000,ans=-inf;
inline void In(){
cin >> n;
for_(i,1,n){
cin >> a[i];
if(!a[i])
a[i] = -1;
a[i] += a[i-1];
if(!q[a[i]+m])
q[a[i]+m] = i;
}
for_(i,1,n){
if(!a[i])
ans = max(ans,i);
else
ans = max(ans,i-q[a[i]+m]);
}
cout << ans;
}
T2 string
没看懂，没写，感觉打个 dfs 能拿分，正解一眼是 dp
T3 bignumber
这题是原，我做过
直接线段树+二分即可
int tot[N],A[N],m,n,q;
inline void add(int a,int val,int q,int l,int r){
if(l==r){
tot[q]=val;
return;
}
if(mid(l,r)>=a)
add(a,val,q*2,l,mid(l,r));
if(mid(l,r)<a)
add(a,val,q*2+1,mid(l,r)+1,r);
tot[q]=max(tot[q*2],tot[q*2+1]);
}
inline int ask(int lc,int rc,int q,int l,int r){
if(lc<=l&&r<=rc)
return tot[q];
int maxa=-inf,maxb=-inf;
if(lc<=mid(l,r))
maxa=ask(lc,rc,q*2,l,mid(l,r));
if(mid(l,r)<rc)
maxb=ask(lc,rc,q*2+1,mid(l,r)+1,r);
return max(maxa,maxb);
}
inline void In(){
int a;
cin >> a >> m;
for_(i,1,a){
char ans;int qwq;
cin >> ans >> qwq;
if(ans=='A'){
add(n+1,(qwq+q)%m,1,1,a);
n++;
}
else{
cout << (q=ask(n-qwq+1,n,1,1,a)) << endl;
}
}
}