最大流Dinic模板

此模板未验证正确性，抄书型模板，慎用。

struct Edge{
int from, to, cap, flow;
};

int dfs(int x, int a);

struct Dinic{
int n, m, s, t;             //结点数，边数（包括反向弧），原点编号和汇点编号 
vector<Edge> edges;         //边表。edges[e]和edges[e^1]互为反向弧
vector<int> g[N];           //邻接表。
bool vis[N];
int d[N];                   //从起点到i的距离
int cur[N];                 //当前弧下标

void Add_edge(int from, int to, int cap){
        edges.push_back((Edge) {from, to, cap, 0});
        edges.push_back((Edge) {to, from, 0, 0});
        m = edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }

bool bfs(){
memset(vis, 0, sizeof(vis));
queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0; i < g[x].size(); i++){
                Edge& e = edges[g[x][i]];
if(!vis[e.to] && e.cap > e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
return vis[t];
    }

int Maxflow(int s, int t){
this->s = s; this->t = t;
int flow = 0;
while(bfs()){
memset(cur, 0, sizeof(cur));
            flow += dfs(s, inf);
        }
return flow;
    }
};

int dfs(int x, int a){
if(x == t || a == 0) return a;
int flow = 0, f;
for(int& i = cur[x]; i < g[x].size(); i++){
        Edge& e = edges[g[x][i]];
if(d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0 ){
            e.flow += f;
            edges[g[x][i]^1].flow -= f;
            flow += f;
            a -= f;
if(a == 0) break;
        }
    }
return flow;
}