(Sky OJ) 151. Day 4 PC. 西西瓦賽跑

https://pc2.tfcis.org/sky/index.php/problem/view/151/

Dinic Flow

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

typedef long long LL;

struct Dinic {
    static const int MAX_N = 4e4 + 6;
    struct Edge {
        LL to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    int n,s,t;
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n+1>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N],level[MAX_N];
    void BFS() {
        queue<int> que;
        memset(level,-1,sizeof(level));
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (Edge &e:edg[t]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[t] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    LL dfs(int id,LL flow) {
        if (id == t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                int ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const LL INF = 1e15 + 7;
    LL flow() {
        LL ret=0;
        while (1) {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            LL tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

const int MAX_R = 1e3 + 6;
const int MAX_K = 26;

int x[MAX_R][MAX_K];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int r,k,l;
        scanf("%d %d %d",&r,&k,&l);
        int s=2*r*k,t=2*r*k+1;
        dinic.init(t,s,t);
        int n=r*k;
        for (int i=0;r>i;i++) {
            for (int j=0;k>j;j++) {
                scanf("%d",&x[i][j]);
                //i * k + j
                if (i==0) {
                    dinic.add_edge(s,i*k+j,1);
                }
                if (i==r-1) {
                    dinic.add_edge(i*k+j+n,t,1);
                }
                dinic.add_edge(i*k+j,i*k+j+n,1);
                if (i>0) {
                    for (int kk=0;k>kk;kk++) {
                        if (abs(x[i][j] - x[i-1][kk]) <= l) dinic.add_edge((i-1)*k+kk+n,i*k+j,1);
                    }
                }
            }
        }
        printf("%d\n",dinic.flow());
    }
}