1 算法

1.1 EK-最大流

不断BFS寻找增广路，每次找到后正向边减流逆向边加流

void bae(int u,int v,int w){ae(u,v,w);ae(v,u,0);}
void upd(){
    ans+=dis[t];int u=t;
    while(u!=s){
        int v=lst[u];
        edge[v].qz-=dis[t];
        edge[v^1].qz+=dis[t];
        u=edge[v^1].to;
    }
} 
bool bfs(){
    memset(ck,0,sizeof(ck));
    queue<int> q;q.push(s);
    ck[s]=1;dis[s]=INF;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=edge[i].nxt) {
            if(edge[i].qz<=0) continue;
            int v=edge[i].to;
            if(ck[v]) continue;ck[v]=1;
            dis[v]=min(dis[u],edge[i].qz);
            lst[v]=i;q.push(v);
            if(v==t){upd();return true;}
        }
    }
    return false;
}

1.1.1 将bfs改为SPFA-最小费用最大流

void bae(int u,int v,int w,int uu){ae(u,v,w,uu);ae(v,u,0,-uu);}
void upd(){
    ans+=dis[t];ans2+=dis[t]*sp[t];
    int u=t;
    while(u!=s){
        int v=lst[u];
        edge[v].qz-=dis[t];
        edge[v^1].qz+=dis[t];
        u=edge[v^1].to;
    }
} 
bool spfa(){
    memset(ck,0,sizeof(ck));
    memset(sp,0x3f,sizeof(sp));
    queue<int> q;q.push(s);
    ck[s]=1;dis[s]=INF;sp[s]=0;
    while(q.size()){
        int u=q.front();q.pop();ck[u]=0;
        for(int i=hd[u];i;i=edge[i].nxt) {
            if(edge[i].qz<=0) continue;
            int v=edge[i].to;
            if(sp[v]>sp[u]+edge[i].dis){
                sp[v]=sp[u]+edge[i].dis;
                dis[v]=min(dis[u],edge[i].qz);
                lst[v]=i;if(!ck[v]){ck[v]=1;q.push(v);}
            }
        }
    }
    if(sp[t]<100000000){upd();return true;}
    return false;
}

1.2 Dinic-最大流

建立分层图，使用dfs一次求出多个增广路，搭配上各种优化以达到比EK更优的算法

bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;q.push(s);dep[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=edge[i].nxt) {
            if(edge[i].qz<=0) continue;
            int v=edge[i].to;
            if(dep[v]) continue;dep[v]=dep[u]+1;
            if(v==t){return true;}
            q.push(v);
        }
    }
    return false;
}
int dfs(int u,int sm){
    if(u==t) return sm;
    int result=0;
    for(int i=st[u];i;i=edge[i].nxt) {
        st[u]=i;
        if(edge[i].qz<=0) continue;
        int v=edge[i].to;
        if(dep[v]!=dep[u]+1) continue;
        int res=dfs(v,min(sm,edge[i].qz));
        if(!res) dep[v]=0;
        edge[i].qz-=res;edge[i^1].qz+=res;
        result+=res;sm-=res;
        if(!sm) break;
    }
    return result;
}
//....main
while(bfs()){
    for(int i=1;i<=n;i++) st[i]=hd[i];
    ans+=dfs(s,INF);
}

1.3 ISAP-最大流

还没学

2 例题

2.1 最大流

2.1.1 P2740-[USACO4.2] 草地排水Drainage Ditches

EK/Dinic模板，不再多讲

2.1.2 P3386-【模板】二分图最大匹配

虽然可以用匈牙利但是也能当作Dinic练习
下述所有建边边权都为1
建立超级源点与超级汇点，源点连接前n个数，后m个数连接汇点
然后正常连边，最后跑一遍Dinic即可
以下定义x向y连边(z)为由x向y连接权值为z的单向边

2.1.3 P3254-圆桌问题

源点向代表团连边(代表团人数)
建nm条边从代表团向圆桌
圆桌向汇点连边(圆桌人数)
最大流为总人数有解，输出方案不细说

2.1.4 P6768-[USACO05MAR] Ombrophobic Bovines 发抖的牛

Floyd求全源最短路(其他算法也可)
二分最终答案，每次二分建边如下：
1.源点向[田地1]连边(牛数)
2.[田地2]向汇点连边(雨棚容量)
3.题目给出的边(INF)，前提是行走时间<=二分目标
每次都跑一遍Dinic

2.1.5 P2891-[USACO07OPEN] Dining G

对于每个水果i: 源点向i连边(1)
对于每个饮料i: i向汇点连边(1)
对于每个奶牛i喜欢水果j: j向[i_1]连边(1)
对于每个奶牛i喜欢饮料j: [i_2]向j连边(1)
跑Dinic

2.1.6 P3425-[POI2005] KOS-

二分答案，目标mid:
对于每场游戏i，在a,b之间：
源点向i连边(1)
i向a连边(1),i向b连边(1)
对于每个人j，j向汇点连边(mid)
如果Dinic最大流为游戏数量则有解
输出解看那一条边权值是否被更新为0

2.1.7 P4638-[SHOI2011] 银行家

是双倍经验，SP4063-MPIGS-Sell Pigs
对于第i个人要打开第j个保险箱：
如果保险箱没打开过，源点向i连边(保险箱钱数)
如果保险箱打开过，上个打开的人连边向i连边(INF)
对于每个人i，i向汇点连边(希望获得钱数)

2.1.8 P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

对于第i个人：
如果意愿为1，源点向i连边(1)
如果意愿为0，i向汇点连边(1)
对于第i个人与第j个人的朋友关系：
互相连边(1)

2.1.9* War

题面：求最短路径条数
待解答

2.1.10* P2774-方格取数问题

待解答

2.2 费用流

以下定义x向y连边(z,w)为由x向y连接权值为z费用为w的单向边

2.2.1 P4015-运输问题

对于仓库i，源点向i连边(存储量,0)
对于零售店j，j向汇点连边(需求量,0)
对于仓库i向零售店j供货，i向j连边(INF,费用)

2.2.2 P2053-[SCOI2007] 修车

工人i切成m个点（i_1~i_m）
对于顾客i找工人j修车：
i向j_k连边(1,k×费用)
对于顾客i，源点向i连边(1,0)
对于工人i，i_m向汇点连边(1,0)

2.2.3* 方格取数2

题面：给定一个n×n的矩阵，矩阵方格中有数，每次可以从一个格子走到向下或向右的格子并取走格子上的数，现在求两条从左上角到右下角的不相交的路径，使取走的数的和最大。
待解答

2.2.4* P1251-餐巾计划问题

待解答

B 下午的月赛(成绩rk6)

B.1 color

累加得到估值，判断即可

B.2 drink

找编号最小的1与编号最大的1，计算一共有几个

B.3 queue

比较水的模拟，注意细节

B.4 queue

明显二分答案，问题是如何判定
考虑二次差分，结果发现每次至多修改4个数字