奋战冬三月昨日跑操排名

第一名...第二名....第三名....倒第一....到第二....到第三....

奋战冬三月昨日扣分明细

xx班有人掉队扣30分

xx班有人拒报学号扣30分

....

好各班，操前班呼！

一班，跑步，走！

2班跟上！

....

9班和十班的班距缩小！！

十一班十二班缩小班距！跟上！

13班口号声音很响！
....

20班留下检查人数，检查完来国旗下集合

各班体委跑操后来国旗下集合，我们开个短会

...

出口处不要走！跑步进入班级，哪个班级走，我们不记学号，只记班级直接扣30分，让他们班倒第一！

....

加权的班级记得加权！哪个班级不加直接扣20分！

学生会记得检查

放音乐的同学音乐停一下

最大流

Edmond_Karp 增广路

下面简称EK

若一条从源点\(S\)到汇点\(T\)的路径上各条边的剩余容量为\(0\)，则称这条路径是一条增广路

显然可以让流沿着增广路从\(S\)流到\(T\)使网络流量增大

EK的算法思想就是BFS寻找增广路，直到网络上不存在增广路为止

在每轮寻找增广路时EK只考虑图中所有\(f(x,y) < c(x,y)\) 的边并用BFS寻找到一条\(S\)到\(T\)的包含边数最少的路径并记录路径上各边的剩余容量的最小值\(m\)，则网络的流量可以增加\(m\)

当一条边的流量\(f(x,y)>0\)时它的反向边\(f(y,x) < c(y,x)\)所以EK还需要遍历\(E\)中每条边的反向边

时间复杂度\(O(nm^2)\)

看的我直接暴毙了

然后去查发现能优化

将 \(G\) 中所有结点和剩余容量大于 \(0\) 的边构成的子图称为残量网络 \(G_f\) ，即 \(G_f=(V,E_f)\) ，其中 \(E_f=\left\{(u,v) \mid c_f(u,v)>0\right\}\)。

然后EK每轮都可能会遍历整个参量网络，但只找出一条增广路，给我看恼了

Dinic
- 前言:
  
  没看太懂，完全瞎写的，毫无参考价值

首先在BFS中有一个节点的层次\(d[x]\)代表从\(S\)到\(x\)的最少要经过的边数

在残量网络中满足\(d[y]=d[x]+1\)的边\((x,y)\)构成的子图称作分层图

分层图明显是一个DAG然后就可以重复以下几个操作

在残量网络中BFS求出节点的层次构造分层图
在分层图里DFS寻找增广路在回溯时实时更新剩余容量
重复以上操作直到残量网络中\(S\)无法到达\(T\)

K8的学习笔记摘录以下

无用点优化

如果有流量流向一个点的时候这个点流不动了，说明它在当前分层图上不再能做出贡献，可以暂时删去。

当前弧优化

决定复杂度，不会负优化，你慢了说明你挂了。

如果当前到点 \(u\) 的流在 \(u\) 遍历完其指向的所有点时用完了，我们记录一下是推向哪条边时用完的，下次再搜索到 \(u\) 时直接从这条边开始推，因为之前的肯定推满了。

然后就是复杂度\(O(n^2m)\)，但是一般远远达不到这个上界

代码(不知道是不是对的)

#include<bits/stdc++.h>
#define int long long
const int INF = 0x66CCFF0712;
const int MAXM = 0X66CCFF;
const int MAXN = 0X6CF;
const int maxm = 50010;
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
struct graph{
    int ver,edge,Next;
}T[MAXM];
int head[MAXM],d[maxm],now[maxm],n,m,s,t,tot,max;
std::queue<int> q;
namespace Graph{
    void add(int x,int y,int z){
        T[++tot].ver = y;
        T[tot].edge = z;
        T[tot].Next = head[x];
        head[x] = tot;

        T[++tot].ver = x;
        T[tot].edge = 0;
        T[tot].Next = head[y];
        head[y] = tot;
    }
    inline bool bfs(){
        memset(d,0,sizeof(d));
        while(q.size()) 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=T[i].Next)
                if(T[i].edge && !d[T[i].ver]){
                    q.push(T[i].ver);
                    now[T[i].ver] = head[T[i].ver];
                    d[T[i].ver] = d[x]+1;
                    if(T[i].ver == t)return 1;
                }
        } 
        return 0;
    }
    inline int dinic(int x,int flow){
        if(x == t) return flow;
        int rest = flow,k;
        for(int i=now[x] ; i&&rest ; i=T[i].Next){
            now[x] = i;
            if(T[i].edge && d[T[i].ver]==d[x]+1){
                k = dinic(T[i].ver,std::min(rest,T[i].edge));
                if(!k) d[T[i].ver]=0;
                T[i].edge -= k;
                T[i^1].edge += k;
                rest -= k;
            }
        }
        return flow-rest;
    }
}
signed main(){
    n=read(),m=read(),s=read(),t=read();
    tot=1;
    for(int i=1;i<=m;i++) Graph::add(read(),read(),read());
    int flow=0;
    while(Graph::bfs())
        while(flow=Graph::dinic(s,INF))
            max+=flow;
    write(max);
}