图论算法模板整理

//无向图的双连通分量int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; // 割顶的bccno无意义struct Edge { int u, v; };vector<int> G[maxn], bcc[maxn];stack<Edge> S;int dfs(int u, int fa) {  int lowu = pre[u] = ++dfs_clock;  int child = 0;  for(int i = 0; i < G[u].size(); i++) {    int v = G[u][i];    Edge e = (Edge){u, v};    if(!pre[v]) { // 没有访问过v      S.push(e);      child++;      int lowv = dfs(v, u);      lowu = min(lowu, lowv); // 用后代的low函数更新自己      if(lowv >= pre[u]) {        iscut[u] = true;        bcc_cnt++; bcc[bcc_cnt].clear();        for(;;) {          Edge x = S.top(); S.pop();          if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }          if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }          if(x.u == u && x.v == v) break;        }      }    }    else if(pre[v] < pre[u] && v != fa) {      S.push(e);      lowu = min(lowu, pre[v]); // 用反向边更新自己    }  }  if(fa < 0 && child == 1) iscut[u] = 0;  return lowu;}void find_bcc(int n) {  // 调用结束后S保证为空，所以不用清空  memset(pre, 0, sizeof(pre));  memset(iscut, 0, sizeof(iscut));  memset(bccno, 0, sizeof(bccno));  dfs_clock = bcc_cnt = 0;  for(int i = 0; i < n; i++)    if(!pre[i]) dfs(i, -1); };//无向图求桥 & 双连通分量int dfs(int u, int fa)  {      int lowu = pre[u] = ++dfs_clock;      int nc = G[u].size();      REP(i, nc)      {          int v = edges[G[u][i]].to;          if(!pre[v])          {              int lowv = dfs(v, u);              lowu = min(lowu, lowv);              if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; //标记所有桥          }          else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);      }      return low[u] = lowu;  }    void dfs1(int u)  {      bccno[u] = bcc_cnt;      int nc = G[u].size();      REP(i, nc)      {          int v = edges[G[u][i]].to;          if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);//不经过桥      }  }    void find_bcc()  {      CLR(pre, 0); CLR(bccno, 0);      dfs_clock = bcc_cnt = 0;      REP(i, n) if(!pre[i]) dfs(i, -1);      REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i);  }  //有向图的强连通分量vector<int> G[maxn];int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;stack<int> S;void dfs(int u) {  pre[u] = lowlink[u] = ++dfs_clock;  S.push(u);  for(int i = 0; i < G[u].size(); i++) {    int v = G[u][i];    if(!pre[v]) {      dfs(v);      lowlink[u] = min(lowlink[u], lowlink[v]);    } else if(!sccno[v]) {      lowlink[u] = min(lowlink[u], pre[v]);    }  }  if(lowlink[u] == pre[u]) {    scc_cnt++;    for(;;) {      int x = S.top(); S.pop();      sccno[x] = scc_cnt;      if(x == u) break;    }  }}void find_scc(int n) {  dfs_clock = scc_cnt = 0;  memset(sccno, 0, sizeof(sccno));  memset(pre, 0, sizeof(pre));  for(int i = 0; i < n; i++)    if(!pre[i]) dfs(i);};//无向图的欧拉回路 保存在G中void add(int u, int v){    g[u][v] = g[v][u] = 1;     degree[u]++, degree[v]++; }void Euler()  {      FF(i, 1, n+1) if(degree[i])      {          int u = i;          while(true)          {              FF(j, 1, n+1) if(g[u][j] && g[j][u])              {                  g[j][u] = 0;                  degree[u]--, degree[i]--;                  u = j;                  break;              }              if(u == i) break;          }      }  } //2-sat dfs版本struct TwoSAT {  int n;  vector<int> G[maxn*2];  bool mark[maxn*2];  int S[maxn*2], c;  bool dfs(int x) {    if (mark[x^1]) return false;    if (mark[x]) return true;    mark[x] = true;    S[c++] = x;    for (int i = 0; i < G[x].size(); i++)      if (!dfs(G[x][i])) return false;    return true;  }  void init(int n) {    this->n = n;    for (int i = 0; i < n*2; i++) G[i].clear();    memset(mark, 0, sizeof(mark));  }  // x = xval or y = yval  void add_clause(int x, int xval, int y, int yval) {    x = x * 2 + xval;    y = y * 2 + yval;    G[x^1].push_back(y);    G[y^1].push_back(x);  }  bool solve() {    for(int i = 0; i < n*2; i += 2)      if(!mark[i] && !mark[i+1]) {        c = 0;        if(!dfs(i)) {          while(c > 0) mark[S[--c]] = false;          if(!dfs(i+1)) return false;        }      }    return true;  }};//堆优化的Dijkstrastruct Edge {  int from, to, 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[maxn];  bool done[maxn];    // 是否已永久标号  int d[maxn];        // s到各个点的距离  int p[maxn];        // 最短路中的上一条弧  void init(int n) {    this->n = n;    for(int i = 0; i < n; i++) G[i].clear();    edges.clear();  }  void AddEdge(int from, int to, int dist) {    edges.push_back((Edge){from, to, dist});    m = edges.size();    G[from].push_back(m-1);  }  void dijkstra(int 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;          p[e.to] = G[u][i];          Q.push((HeapNode){d[e.to], e.to});        }      }    }  }  // dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）  void GetShortestPaths(int s, int* dist, vector<int>* paths) {    dijkstra(s);    for(int i = 0; i < n; i++) {      dist[i] = d[i];      paths[i].clear();      int t = i;      paths[i].push_back(t);      while(t != s) {        paths[i].push_back(edges[p[t]].from);        t = edges[p[t]].from;      }      reverse(paths[i].begin(), paths[i].end());    }  }};//spfa判负环struct Edge {  int from, to;  double dist;};struct spfa {  int n, m;  vector<Edge> edges;  vector<int> G[maxn];  bool inq[maxn];     // 是否在队列中  double d[maxn];     // s到各个点的距离  int p[maxn];        // 最短路中的上一条弧  int cnt[maxn];      // 进队次数  void init(int n) {    this->n = n;    for(int i = 0; i < n; i++) G[i].clear();    edges.clear();  }  void AddEdge(int from, int to, double dist) {    edges.push_back((Edge){from, to, dist});    m = edges.size();    G[from].push_back(m-1);  }  bool negativeCycle() {    queue<int> Q;    memset(inq, 0, sizeof(inq));    memset(cnt, 0, sizeof(cnt));    for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); }    while(!Q.empty()) {      int u = Q.front(); Q.pop();      inq[u] = false;      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;          p[e.to] = G[u][i];          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }        }      }    }    return false;  }};//kruskal求次小生成树 maxcost[i][j]为i->j的瓶颈路 //对于MST边u, v maxcost[u][v] = 0int n, m, x[maxn], y[maxn], p[maxn];int pa[maxn];int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } //G保存MST C保存MST边权vector<int> G[maxn];vector<double> C[maxn];struct Edge {  int x, y;  double d;  bool operator < (const Edge& rhs) const {    return d < rhs.d;  }};Edge e[maxn*maxn];double maxcost[maxn][maxn];vector<int> nodes;void dfs(int u, int fa, double facost) {  for(int i = 0; i < nodes.size(); i++) {    int x = nodes[i];    maxcost[u][x] = maxcost[x][u] = max(maxcost[x][fa], facost);  }  nodes.push_back(u);  for(int i = 0; i < G[u].size(); i++) {    int v = G[u][i];    if(v != fa) dfs(v, u, C[u][i]);  }}double MST() {  sort(e, e+m);  for(int i = 0; i < n; i++) { pa[i] = i; G[i].clear(); C[i].clear(); }  int cnt = 0;  double ans = 0;  for(int i = 0; i < m; i++) {    int x = e[i].x, y = e[i].y, u = findset(x), v = findset(y);    double d = e[i].d;    if(u != v) {      pa[u] = v;      G[x].push_back(y); C[x].push_back(d);      G[y].push_back(x); C[y].push_back(d);      ans += d;      if(++cnt == n-1) break;    }  }  return ans;}//prim求次小生成树//use[u][v] = 2时，边<u, v>在MST上//use[u][v] = 1时，原图存在边<u, v>。//f[u][v]表示u->v的最小瓶颈路 初始化为0double prim()  {      int pre[maxn] = {-1};      bool vis[maxn] = {0};      double d[maxn], ret = 0;      FF(i, 1, n+1) d[i] = INF;   d[1] = 0;      FF(i, 1, n+1)      {          int pos;          double tmp = INF;          FF(j, 1, n+1) if(!vis[j] && d[j] < tmp) tmp = d[j], pos = j;          if(pre[pos] != -1)          {              use[pre[pos]][pos] = use[pos][pre[pos]] = 2;              FF(j, 1, n+1) if(vis[j]) f[pos][j] = f[j][pos] = max(f[j][pre[pos]], g[pre[pos]][pos]);          }          vis[pos] = 1;          ret += d[pos];          FF(j, 1, n+1) if(!vis[j] && use[pos][j] && g[pos][j] < d[j]) d[j] = g[pos][j], pre[j] = pos;      }      return ret;  }//LCAstruct LCA {  int n;  int fa[maxn];   // 父亲数组  int cost[maxn]; // 和父亲的费用  int L[maxn];    // 层次（根节点层次为0）  int anc[maxn][logmaxn];     // anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i]  int maxcost[maxn][logmaxn]; // maxcost[p][i]是i和anc[p][i]的路径上的最大费用  // 预处理，根据fa和cost数组求出anc和maxcost数组  void preprocess() {    for(int i = 0; i < n; i++) {      anc[i][0] = fa[i]; maxcost[i][0] = cost[i];      for(int j = 1; (1 << j) < n; j++) anc[i][j] = -1;    }       for(int j = 1; (1 << j) < n; j++)      for(int i = 0; i < n; i++)        if(anc[i][j-1] != -1) {          int a = anc[i][j-1];          anc[i][j] = anc[a][j-1];          maxcost[i][j] = max(maxcost[i][j-1], maxcost[a][j-1]);        }  }  // 求p到q的路径上的最大权  int query(int p, int q) {    int tmp, log, i;    if(L[p] < L[q]) swap(p, q);    for(log = 1; (1 << log) <= L[p]; log++); log--;    int ans = -INF;    for(int i = log; i >= 0; i--)      if (L[p] - (1 << i) >= L[q]) { ans = max(ans, maxcost[p][i]); p = anc[p][i];}       if (p == q) return ans; // LCA为p       for(int i = log; i >= 0; i--)      if(anc[p][i] != -1 && anc[p][i] != anc[q][i]) {        ans = max(ans, maxcost[p][i]); p = anc[p][i];        ans = max(ans, maxcost[q][i]); q = anc[q][i];      }    ans = max(ans, cost[p]);    ans = max(ans, cost[q]);    return ans; // LCA为fa[p]（它也等于fa[q]）  }  };//固定根的最小树型图，邻接矩阵写法struct MDST {    int n;  int w[maxn][maxn]; // 边权  int vis[maxn];     // 访问标记，仅用来判断无解  int ans;           // 计算答案  int removed[maxn]; // 每个点是否被删除  int cid[maxn];     // 所在圈编号  int pre[maxn];     // 最小入边的起点  int iw[maxn];      // 最小入边的权值  int max_cid;       // 最大圈编号  void init(int n) {    this->n = n;    for(int i = 0; i < n; i++)      for(int j = 0; j < n; j++) w[i][j] = INF;  }  void AddEdge(int u, int v, int cost) {    w[u][v] = min(w[u][v], cost); // 重边取权最小的  }  // 从s出发能到达多少个结点  int dfs(int s) {    vis[s] = 1;    int ans = 1;    for(int i = 0; i < n; i++)      if(!vis[i] && w[s][i] < INF) ans += dfs(i);    return ans;  }  // 从u出发沿着pre指针找圈  bool cycle(int u) {    max_cid++;    int v = u;    while(cid[v] != max_cid) { cid[v] = max_cid; v = pre[v]; }    return v == u;  }  // 计算u的最小入弧，入弧起点不得在圈c中  void update(int u) {    iw[u] = INF;    for(int i = 0; i < n; i++)      if(!removed[i] && w[i][u] < iw[u]) {        iw[u] = w[i][u];        pre[u] = i;      }  }  // 根结点为s，如果失败则返回false  bool solve(int s) {        memset(vis, 0, sizeof(vis));    if(dfs(s) != n) return false;    memset(removed, 0, sizeof(removed));    memset(cid, 0, sizeof(cid));    for(int u = 0; u < n; u++) update(u);    pre[s] = s; iw[s] = 0; // 根结点特殊处理    ans = max_cid = 0;    for(;;) {      bool have_cycle = false;      for(int u = 0; u < n; u++) if(u != s && !removed[u] && cycle(u)){        have_cycle = true;        // 以下代码缩圈，圈上除了u之外的结点均删除        int v = u;        do {          if(v != u) removed[v] = 1;          ans += iw[v];          // 对于圈外点i，把边i->v改成i->u（并调整权值）；v->i改为u->i          // 注意圈上可能还有一个v'使得i->v'或者v'->i存在，因此只保留权值最小的i->u和u->i          for(int i = 0; i < n; i++) if(cid[i] != cid[u] && !removed[i]) {            if(w[i][v] < INF) w[i][u] = min(w[i][u], w[i][v]-iw[v]);            w[u][i] = min(w[u][i], w[v][i]);            if(pre[i] == v) pre[i] = u;          }          v = pre[v];        } while(v != u);                update(u);        break;      }      if(!have_cycle) break;    }    for(int i = 0; i < n; i++)      if(!removed[i]) ans += iw[i];    return true;  }};//KM int W[maxn][maxn], n;int Lx[maxn], Ly[maxn]; // 顶标int left[maxn];         // left[i]为右边第i个点的匹配点编号bool S[maxn], T[maxn];   // S[i]和T[i]为左/右第i个点是否已标记bool match(int i){  S[i] = true;  for(int j = 1; j <= n; j++) if (Lx[i]+Ly[j] == W[i][j] && !T[j]){    T[j] = true;    if (!left[j] || match(left[j])){      left[j] = i;      return true;    }  }  return false;}void update(){  int a = INF;  for(int i = 1; i <= n; i++) if(S[i])    for(int j = 1; j <= n; j++) if(!T[j])      a = min(a, Lx[i]+Ly[j] - W[i][j]);  for(int i = 1; i <= n; i++) {    if(S[i]) Lx[i] -= a;    if(T[i]) Ly[i] += a;  }}void KM() {  for(int i = 1; i <= n; i++) {    left[i] = Lx[i] = Ly[i] = 0;    for(int j = 1; j <= n; j++)      Lx[i] = max(Lx[i], W[i][j]);  }  for(int i = 1; i <= n; i++) {    for(;;) {      for(int j = 1; j <= n; j++) S[j] = T[j] = false;      if(match(i)) break; else update();    }  }}// 二分图最大基数匹配，邻接矩阵写法  struct BPM {  int n, m;               // 左右顶点个数  int G[maxn][maxn];      // 邻接表  int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在  bool T[maxn];           // T[i]为右边第i个点是否已标记  void init(int n, int m) {    this->n = n;    this->m = m;    memset(G, 0, sizeof(G));  }  bool match(int u){    for(int v = 0; v < m; v++) if(G[u][v] && !T[v]) {      T[v] = true;      if (left[v] == -1 || match(left[v])){        left[v] = u;        return true;      }    }    return false;  }  // 求最大匹配  int solve() {    memset(left, -1, sizeof(left));    int ans = 0;    for(int u = 0; u < n; u++) { // 从左边结点u开始增广      memset(T, 0, sizeof(T));      if(match(u)) ans++;    }    return ans;  }};// 二分图最大基数匹配求覆盖集struct BPM {    int n, m;               // 左右顶点个数    vector<int> G[maxn];    // 邻接表    int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在    bool T[maxn];           // T[i]为右边第i个点是否已标记      int right[maxn];        // 求最小覆盖用    bool S[maxn];           // 求最小覆盖用      void init(int n, int m) {      this->n = n;      this->m = m;      for(int i = 0; i < n; i++) G[i].clear();    }      void AddEdge(int u, int v) {      G[u].push_back(v);    }      bool match(int u){      S[u] = true;      for(int i = 0; i < G[u].size(); i++) {        int v = G[u][i];        if (!T[v]){          T[v] = true;          if (left[v] == -1 || match(left[v])){            left[v] = u;            right[u] = v;            return true;          }        }      }      return false;    }      // 求最大匹配    int solve() {      memset(left, -1, sizeof(left));      memset(right, -1, sizeof(right));      int ans = 0;      for(int u = 0; u < n; u++) { // 从左边结点u开始增广        memset(S, 0, sizeof(S));        memset(T, 0, sizeof(T));        if(match(u)) ans++;      }      return ans;    }      // 求最小覆盖。X和Y为最小覆盖中的点集    int mincover(vector<int>& X, vector<int>& Y) {      int ans = solve();      memset(S, 0, sizeof(S));      memset(T, 0, sizeof(T));      for(int u = 0; u < n; u++)        if(right[u] == -1) match(u); // 从所有X未盖点出发增广      for(int u = 0; u < n; u++)        if(!S[u]) X.push_back(u); // X中的未标记点      for(int v = 0; v < m; v++)        if(T[v]) Y.push_back(v);  // Y中的已标记点     return ans;    }  };//ISAPstruct Edge {    int from, to, cap, flow;  };bool operator < (const Edge& a, const Edge& b) {    return a.from < b.from || (a.from == b.from && a.to < b.to);  }    struct ISAP {    int n, m, s, t;    vector<Edge> edges;    vector<int> G[maxn];   // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号    bool vis[maxn];        // BFS使用    int d[maxn];           // 从起点到i的距离    int cur[maxn];        // 当前弧指针    int p[maxn];          // 可增广路上的上一条弧    int num[maxn];        // 距离标号计数      void AddEdge(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(t);      vis[t] = 1;      d[t] = 0;      while(!Q.empty()) {        int x = Q.front(); Q.pop();        for(int i = 0; i < G[x].size(); i++) {          Edge& e = edges[G[x][i]^1];          if(!vis[e.from] && e.cap > e.flow) {            vis[e.from] = 1;            d[e.from] = d[x] + 1;            Q.push(e.from);          }        }      }      return vis[s];    }      void ClearAll(int n) {      this->n = n;      for(int i = 0; i < n; i++) G[i].clear();      edges.clear();    }      void ClearFlow() {      for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;        }      int Augment() {      int x = t, a = INF;      while(x != s) {        Edge& e = edges[p[x]];        a = min(a, e.cap-e.flow);        x = edges[p[x]].from;      }      x = t;      while(x != s) {        edges[p[x]].flow += a;        edges[p[x]^1].flow -= a;        x = edges[p[x]].from;      }      return a;    }      int Maxflow(int s, int t, int need) {      this->s = s; this->t = t;      int flow = 0;      BFS();      memset(num, 0, sizeof(num));      for(int i = 0; i < n; i++) num[d[i]]++;      int x = s;      memset(cur, 0, sizeof(cur));      while(d[s] < n) {        if(x == t) {          flow += Augment();          if(flow >= need) return flow;          x = s;        }        int ok = 0;        for(int i = cur[x]; i < G[x].size(); i++) {          Edge& e = edges[G[x][i]];          if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance            ok = 1;            p[e.to] = G[x][i];            cur[x] = i; // 注意            x = e.to;            break;          }        }        if(!ok) { // Retreat          int m = n-1; // 初值注意          for(int i = 0; i < G[x].size(); i++) {            Edge& e = edges[G[x][i]];            if(e.cap > e.flow) m = min(m, d[e.to]);          }          if(--num[d[x]] == 0) break;          num[d[x] = m+1]++;          cur[x] = 0; // 注意          if(x != s) x = edges[p[x]].from;        }      }      return flow;    }      vector<int> Mincut() { // call this after maxflow      BFS();      vector<int> ans;      for(int i = 0; i < edges.size(); i++) {        Edge& e = edges[i];        if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i);      }      return ans;    }      void Reduce() {      for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow;    }      void print() {      printf("Graph:\n");      for(int i = 0; i < edges.size(); i++)        printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow);    }};//Dinicstruct Edge {    int from, to, cap, flow;  };  bool operator < (const Edge& a, const Edge& b) {    return a.from < b.from || (a.from == b.from && a.to < b.to);  }struct Dinic {    int n, m, s, t;    vector<Edge> edges;    // 边数的两倍    vector<int> G[maxn];   // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号    bool vis[maxn];        // BFS使用    int d[maxn];           // 从起点到i的距离    int cur[maxn];         // 当前弧指针      void ClearAll(int n) {      for(int i = 0; i < n; i++) G[i].clear();      edges.clear();    }      void ClearFlow() {      for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;        }      void AddEdge(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);      vis[s] = 1;      d[s] = 0;      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 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;    }      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;    }  };//MCMFstruct Edge {    int from, to, cap, flow, cost;  };struct MCMF {    int n, m, s, t;    vector<Edge> edges;    vector<int> G[maxn];    int inq[maxn];         // 是否在队列中    int d[maxn];           // Bellman-Ford    int p[maxn];           // 上一条弧    int a[maxn];           // 可改进量      void init(int n) {      this->n = n;      for(int i = 0; i < n; i++) G[i].clear();      edges.clear();    }      void AddEdge(int from, int to, int cap, int cost) {      edges.push_back((Edge){from, to, cap, 0, cost});      edges.push_back((Edge){to, from, 0, 0, -cost});      m = edges.size();      G[from].push_back(m-2);      G[to].push_back(m-1);    }      bool BellmanFord(int s, int t, LL& ans) {      for(int i = 0; i < n; i++) d[i] = INF;      memset(inq, 0, sizeof(inq));      d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;        queue<int> Q;      Q.push(s);      while(!Q.empty()) {        int u = Q.front(); Q.pop();        inq[u] = 0;        for(int i = 0; i < G[u].size(); i++) {          Edge& e = edges[G[u][i]];          if(e.cap > e.flow && d[e.to] > d[u] + e.cost) {            d[e.to] = d[u] + e.cost;            p[e.to] = G[u][i];            a[e.to] = min(a[u], e.cap - e.flow);            if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }          }        }      }      if(d[t] == INF) return false;//s-t不连通 失败退出      if(d[t] > 0) return false;//不固定流量的最小费用流      ans += (LL)d[t] * (LL)a[t];      int u = t;      while(u != s) {        edges[p[u]].flow += a[t];        edges[p[u]^1].flow -= a[t];        u = edges[p[u]].from;            }      return true;    }      // 需要保证初始网络中没有负权圈    LL Mincost(int s, int t) {      LL cost = 0;      while(BellmanFord(s, t, cost));      return cost;    }    };