[板子]ISAP

时间:2020-12-13 09:15:24

ISAP求最大流,敲了一发板子,无压行,教程略去。转载请随意。

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <vector>
 using namespace std;

 ;
 const int inf = 0x33333333;

 struct edge {
     int to, rev, cap;
 };

 int n;
 vector<edge> G[maxn];

 void add_edge(int u, int v, int cap) {
     G[u].push_back((edge){v, (int)G[v].size(), cap});
     G[v].push_back((edge){u, (, });
 }

 int isap(int s, int t) {
     //init
     static int h[maxn];    //距离标号
     static int cnt[maxn];  //距离标号计数
     static int cur[maxn];  //当前弧
     static int pv[maxn];   //上一个顶点
     static int pe[maxn];   //上一条弧
     memset(h, , sizeof h);
     memset(cnt, , sizeof cnt);
     cnt[] = n;
     memset(cur, , sizeof cur);
     //solve
     int u = s;
     ;
     while(true) {
         if(u == t) {
             //augment
             int newflow = inf;
             for(int x = t; x != s; x = pv[x]) {
                 edge &e = G[pv[x]][pe[x]];
                 newflow = min(newflow, e.cap);
             }
             flow += newflow;
             for(int x = t; x != s; x = pv[x]) {
                 edge &e = G[pv[x]][pe[x]];
                 e.cap -= newflow;
                 G[x][e.rev].cap += newflow;
             }
             u = s;
         }
         bool did = false;
         for(int &i = cur[u]; i < (int)G[u].size(); ++i) {
             edge &e = G[u][i];
              && h[u] == h[e.to] + ) {
                 //advance
                 did = true;
                 pv[e.to] = u;
                 pe[e.to] = i;
                 u = e.to;
                 break;
             }
         }
         if(!did) {
             //retreat
             ;
             ; i < (int)G[u].size(); ++i) {
                 edge &e = G[u][i];
                 ) {
                     newh = min(newh, h[e.to] + );
                 }
             }
             ) {
                 //gap
                 break;
             }
             ++cnt[h[u] = newh];
             if(u != s) {
                 u = pv[u];
             }
         }
     }
     return flow;
 }

 int main(void) {
     int m, source, sink;
     scanf("%d%d%d%d", &n, &m, &source, &sink), --source, --sink;
     ; i < m; ++i) {
         int from, to, cap;
         scanf("%d%d%d", &from, &to, &cap), --from, --to;
         add_edge(from, to, cap);
     }
     printf("%d\n", isap(source, sink));
     ;
 }