2018年,欲学 OI,被某机构骗去学 Python,结果啥都没学到。
2019年末,终于开始学 C++
2021年4月,摆脱了某机构。
2021年9月,未过初赛
2022年6月,中考失败
2022年7月,自招失败
2022年10月,CSP 失败
2022年11月,NOIP 失败
2023年2月25日,我准备开始写下这篇文章,因为我不知道我还能打多久的OI。
也许是一位女同学的长久鼓励(我喜欢她很久了,她也知道),我没有彻底放弃自己,不知道这算不算是各位口中的 npy,但是她对我的帮助是精神上的。她今天(2023年2月25日)和我聊了聊,让我有了重新拿起电脑的勇气,在这之前,我已经两个月没有摸电脑了。
在我是一位选手一点时间里,写下了 3030 余篇题解,8686 篇博客,帮助某机构出了两场模拟赛,在大大小小的网站,累计做了 15001500 多道题,算是留下了自己的痕迹,不能说是出类拔萃,也可以说是一事无成。
半退役好久了,现在在竞赛上的压力小了很多,就随便学点东西吧。
之前老早就学了网络流,发现有个叫上下界网络流的东西,于是打算学一下。
例题:Loj#116
这道题是纯模板,代码比较简单:
signed main(){
scanf("%d%d%d%d",&n,&m,&a,&b);
s=N-1,t=N-2;
for(int i=1;i<=m;i++){
int u,v,l,r;
scanf("%d%d%d%d",&u,&v,&l,&r);
in[v]+=l,in[u]-=l;
add(u,v,r-l);
}
for(int i=1;i<=n;i++){
if(in[i]>0)all+=in[i],add(s,i,in[i]);
else add(i,t,-in[i]);
}
add(b,a,inf);
if(all!=dinic())puts("please go home to sleep");
else{
s=a,t=b;
all=val[tot];
val[tot-1]=val[tot]=0;
printf("%d\n",dinic()+all);
}
return 0;
}
-
新建一对源点汇点
-
先建一个正常的网络流,每条边为上下界的差。
-
记录下每个点的初始入流和出流
-
然后如果那个点是入流更多,那么就从源点补上,否则就将多余流出的流向汇点。
-
理解一下这个过程,如果某个节点入度多了,就从前面凑,如果出度多了,就往后边使命流。每条边的最大承受量就是上限减下限。
现在我们就完成了无源汇上下界网络流的操作了。
例题:Loj#115
有源汇也很简单,只需要再在给定源点汇点的残留网络上跑一遍最大流即可,最后的答案就是最大流+残留网络最大流。
s=a,t=b;
all=val[tot];
val[tot-1]=val[tot]=0;
printf("%d\n",dinic()+all);
于是我们有了理论基础,现在看到我们的洛谷《模板题》:
简单分析一下就可以发现,这道题实际上很简单,就是一个模板,但是输入量有点庞大,细节有亿点多。
对于每一天建立一个节点,每个少女也建立一个节点。
源点向每一天连一条容量为当天限制 D_iDi 的边。
每一天与那一天拍照的少女连一条边,上界 RR,下界 LL。
最后每个少女往汇点连一条,上界 +\infty+∞,下界 GG。
然后跑一边有源汇上下界网络流即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 2145141
#define inf 2147483647
using namespace std;
int n,m;
int au[N],av[N],al[N],ar[N],cnt,all;
int head[N],to[N],nxt[N],val[N],tot,in[N],a,b,s,t;
int d[N];
void add(int u,int v,int w){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
val[tot]=w;
to[++tot]=u;
nxt[tot]=head[v];
head[v]=tot;
val[tot]=0;
}
void addc(int u,int v,int l,int r){
add(u,v,r-l);
in[u]-=l;in[v]+=l;
}
bool bfs(){
queue<int>q;
q.push(s);
memset(d,-1,sizeof(d));
d[s]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
if(!val[i])continue;
int y=to[i];
if(d[y]==-1){
d[y]=d[x]+1;
if(y==t)return 1;
q.push(y);
}
}
}
return 0;
}
int dfs(int x,int a){
if(!a||x==t)return a;
int res=a;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(val[i]&&d[x]+1==d[y]){
int tmp=dfs(y,min(val[i],res));
res-=tmp;
val[i]-=tmp;
val[i^1]+=tmp;
if(res==0)return a;
}
}
if(a==res)d[x]=-1;
return a-res;
}
int dinic(){
int flow=0;
while(bfs())flow+=dfs(s,inf);
return flow;
}
signed main(){
//freopen("P5192_1.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
tot=1,cnt=0;
s=N-3,t=N-4;
a=n+m+1,b=n+m+2;
memset(head,0,sizeof(head));
memset(in,0,sizeof(in));
all=0;
for(int i=1;i<=m;i++){
int g;
scanf("%d",&g);
addc(i+n,b,g,inf);
}
for(int i=1;i<=n;i++){
int c,d;
scanf("%d%d",&c,&d);
add(a,i,d);
for(int j=1;j<=c;j++){
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
addc(i,n+t+1,l,r);
}
}
for(int i=1;i<=m+n+2;i++){
if(in[i]>0){
add(s,i,in[i]);
all+=in[i];
}
if(in[i]<0)add(i,t,-in[i]);
}
add(b,a,inf);
if(all>dinic())puts("-1\n");
else{
all=val[tot];
val[tot]=val[tot-1]=0;
s=a,t=b;
printf("%d\n\n",dinic()+all);
}
}
return 0;
}