动态更新-算法模版合集

图论

最大流

int s=1995,t=1996;
struct gg {
    int u,v,w,next;
}side[maxn*2];
int head[maxn],cnt=1,maxflow,cur[maxn],rk[maxn];
using namespace std;
void insert(int u,int v,int w) {
    struct gg a={u,v,w,head[u]};side[++cnt]=a;head[u]=cnt;
};
bool bfs() {
    memset(rk,0,sizeof(rk));rk[s]=1;
    queue<int>q;q.push(s);
    while(!q.empty()) {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=side[i].next) {
            int v=side[i].v,w=side[i].w;//w为容量
            if(!w||rk[v])continue;
            rk[v]=rk[now]+1;
            q.push(v);
        }
    }
    if(rk[t])return 1;//走得到
    return 0;
}
int dfs(int now,int flow) {//flow为上一个点能传到这里的流量
    if(now==t)return flow;
    int tot=0;
    for(int &i=cur[now];i;i=side[i].next) {//当前弧优化
        int v=side[i].v,w=side[i].w;
        if(!w||rk[v]!=rk[now]+1)continue;
        int sent=dfs(v,min(flow,w));//sent为当前增广的流量
        tot+=sent;//累计答案
        flow-=sent;side[i].w-=sent;side[i^1].w+=sent;//更新残余网络
    }
    return tot;
}
void dinic() {
    while(bfs()) {
        memcpy(cur,head,sizeof(head));//当前弧优化
        maxflow+=dfs(s,inf);
    }
}