程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1569 網絡流dinic 模板

HDU 1569 網絡流dinic 模板

編輯:C++入門知識

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

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


[cpp]
#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()) 
    { 
        while(f = dinic_dfs(S,inf)) 
        { 
            flow += f ; 
        } 
    } 
    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 ; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved