HDU 1569 網絡流dinic 模闆

貼個模闆，以前學的EK算法算起來年紀比我還大一倍了，該換個模闆了。

還有剛才CSDN肯定BUG了。。。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define Rep(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;

struct kdq
{
    int s ,e ,l ,next ;
}ed[Max * 100] ;
int head[Max] ,deep[Max] ,num ;
int qe[Max * 100] ;
void add(int s, int e ,int l )
{
    ed[num].s = s ;
    ed[num].e = e ;
    ed[num].l = l ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;

    ed[num].s = e ;
    ed[num].e = s ;
    ed[num].l = 0 ;
    ed[num].next =head[e] ;
    head[e] = num ++ ;
}
void init()
{
    mem(head,-1) ;
    num = 0 ;
}
int S,T ;
int dinic_bfs()//bfs出每個點的深度
{
    mem(deep,-1) ;
    deep[S] = 0 ;
    int h = 0 , t = 0 ;
    qe[h ++] = S;
    while(h > t)
    {
        int tt = qe[t ++] ;
        for (int i = head[tt] ; ~i ;i = ed[i].next )
        {
            int e = ed[i].e ;
            int l = ed[i].l ;
            if(deep[e] == -1 && l > 0)
            {
                deep[e] = deep[tt] + 1 ;
                qe[h ++] = e ;
            }
        }
    }
    return deep[T] != -1 ;
}

int dinic_dfs(int now ,int f)
{
    if(now == T)
    return f ;
    int flow = 0 ;
    for (int i = head[now] ; ~i ;i = ed[i].next )
    {
        int e = ed[i].e ;
        int l = ed[i].l ;
        if(deep[now] + 1 == deep[e] && l > 0)
        {
            int mm = min(l,f - flow) ;
            int nn = dinic_dfs(e,mm) ;
            flow += nn ;
            ed[i].l -= nn ;
            ed[i ^ 1].l += nn ;
        }
    }
    if(!flow)//該點不需要再周遊
    deep[now] = -2 ;
    return flow ;
}
int dinic()
{
    int flow = 0 ;
    int f = 0 ;
    while(dinic_bfs())
    {
       flow += dinic_dfs(S,inf) ;
    }
    return flow ;
}
int mx[4] = {0,0,1,-1} ;
int my[4] = {1,-1,0,0} ;
int inmap(int x ,int y ,int n ,int m)
{
    if(x > 0 && x <= n && y > 0 &&y <= m )return 1 ;return 0 ;
}
int main()
{
    int n , m ;
    while(cin >> n >> m )
    {
        int sum = 0 ;
        init() ;
        S = 0 ,T = n * m + 1 ;
        for (int i = 1 ; i <= n ; i ++ )
        {
            for (int j = 1 ;j <= m ;j ++ )
            {
                int d ;
                scanf("%d",&d) ;
                sum += d ;
                if((i + j) & 1)
                {
                    add((i - 1) * m + j , T ,d) ;
                    for (int k = 0 ;k < 4 ;k ++ )
                    {
                        int tx = i + mx[k] ;
                        int ty = j + my[k] ;
                        if(inmap(tx,ty,n,m))
                        add((tx - 1 ) * m + ty , (i - 1 ) * m + j , inf) ;
                    }
                }
                else
                {
                    add(S,(i - 1 ) * m + j , d ) ;
                    for (int k = 0 ;k < 4 ;k ++ )
                    {
                        int tx = i + mx[k] ;
                        int ty = j + my[k] ;
                        if(inmap(tx,ty,n,m))
                        add((i - 1 ) * m + j , ( tx - 1 ) * m + ty , inf) ;
                    }
                }
            }
        }
        cout <<sum - dinic() <<endl;
    }
    return 0 ;
}