Dijkstra模板，Dinic模板和sap模板

Dijkstra模板：

struct Edge{
    int from,to;
    int dist;
};
struct HeapNode{
    int d,u;
    bool operator < (const HeapNode& rhs) const{
        return d > rhs.d;
    }
};
struct Dijkstra{
    int n,m;               //点数和边数
    vector<Edge> edges;    //边列表
    vector<int> G[M];     //每个结点出发的边编号（从0开始编号）
    bool done[N];         //是否已永久标号
    int d[N];             //s到各个点的距离
    ll L;

    void init(int n) {
        this->n = n;
        for(int i = 0; i <= m * 2; i++) G[i].clear();//清空邻接表
        edges.clear();//清空边表
    }

    void addEdge(int from, int to, ll dist) {
        //如果是无向图，每条无向边需调用两次AddEdge
        edges.push_back((Edge){from, to, dist});
        m = edges.size();
        G[from].push_back(m - 1);
    }

    void dijkstra(int s) {//求s到所有点的距离
        priority_queue<HeapNode> Q;
        for(int i = 0; i <= n; i++) d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        Q.push((HeapNode){0, s});
        while(!Q.empty()){
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if(done[u]) continue;
            done[u] = true;
            for(int i = 0; i < G[u].size(); i++){
                Edge& e = edges[G[u][i]];
                if(d[e.to] > d[u] + e.dist){
                    d[e.to] = d[u] + e.dist;
                    Q.push((HeapNode){d[e.to], e.to});
                }
            }
        }
    }

}dij；

Dinic模板：

struct Dinic{
    int ec, head[N], first[N], que[N], lev[N];
    int Next[M], to[M], v[M];

    void init() {
        ec = 0;
        memset(first, -1, sizeof(first));
    }

    void addEdge(int a,int b,int c) {
        to[ec] = b;
        v[ec] = c;
        Next[ec] = first[a];
        first[a] = ec++;

        to[ec] = a;
        v[ec] = 0;
        Next[ec] = first[b];
        first[b] = ec++;
    }

    int BFS() {
        int kid, now, f = 0, r = 1, i;
        memset(lev, 0, sizeof(lev));
        que[0] = s, lev[s] = 1;
        while (f < r) {
            now = que[f++];
            for (i = first[now]; i != -1; i = Next[i]) {
                kid = to[i];
                if (!lev[kid] && v[i]) {
                    lev[kid] = lev[now] + 1;
                    if (kid == t) return 1;
                    que[r++] = kid;
                }
            }
        }
        return 0;
    }

    int DFS(int now, int sum) {
        int kid, flow, rt = 0;
        if (now == t) return sum;
        for (int i = head[now]; i != -1 && rt < sum; i = Next[i]) {
            head[now] = i;
            kid = to[i];
            if (lev[kid] == lev[now] + 1 && v[i]) {
                flow = DFS(kid, min(sum - rt, v[i]));
                if (flow) {
                    v[i] -= flow;
                    v[i^1] += flow;
                    rt += flow;
                } else lev[kid] = -1;
            }
        }
        return rt;
    }

    int dinic() {
        int ans = 0;
        while (BFS()) {
            for (int i = 0; i <= n; i++) {
                head[i] = first[i];
            }
            ans += DFS(s, INF);
        }
        return ans;
    }
}din;

sap模板：

template<int nv,int ne>
struct isap{
    int n,size;
    int head[nv];
    int dis[nv],gap[nv],cur[nv],pre[nv];
    int maxflow;

    struct edge{
        int v,w,next;
        edge(){}
        edge(int _v,int _w,int _next):v(_v),w(_w),next(_next){}
    }E[ne];

    void init(int n){
        this->n=n,size=0;
        cl(head,-1);
    }
    void insert(int u,int v,int w){
        E[size]=edge(v,w,head[u]);
        head[u]=size++;
        E[size]=edge(u,0,head[v]);
        head[v]=size++;
    }
    int maxFlow(int src,int des){
        maxflow=0;
        for(int i=0;i<=n;i++){
            dis[i]=gap[i]=0;
            cur[i]=head[i];
        }
        int u=pre[src]=src;
        int aug=0;///or aug=-1
        while(dis[src]<n){
           loop:for(int &i=cur[u];i!=-1;i=E[i].next){
                int v=E[i].v;
                if(E[i].w&&dis[u]==dis[v]+1){
                    aug=min(aug,E[i].w);
                    pre[v]=u;
                    u=v;
                    if(v==des){
                        maxflow+=aug;
                        for(u=pre[u];v!=src;v=u,u=pre[u]){
                            E[cur[u]].w-=aug;
                            E[cur[u]^1].w+=aug;
                        }
                        aug=inf;
                    }
                    goto loop;
                }
            }
            int mdis=n;
            for(int i=head[u];i!=-1;i=E[i].next){
                int v=E[i].v;
                if(E[i].w&&mdis>dis[v]){
                    cur[u]=i;
                    mdis=dis[v];
                }
            }
            if(--gap[dis[u]]==0)break;
            gap[dis[u]=mdis+1]++;
            u=pre[u];
        }
        return maxflow;
    }
};
isap<1005,200005> G;