HDU 1569 方格取數(2)(最大點權獨立集)

[cpp] 
/*
題解：
因為這個數據比較大，所以用動態規劃會超時。
將圖轉換成黑白棋盤問題，i + j 為奇數的與s節點相連，邊的權值為棋盤上對應位置的值，其他的與t節點相連，邊的權值為棋盤上對應位置的值，然後讓棋盤上相鄰之間的節點用邊相連，邊的權值為INF。這樣問題就轉換為了最大點權獨立集問題。
定理：
1、最大點權獨立集 = sum - 最小點權覆蓋集。
2、最小點權覆蓋集 = 最小割 = 最大流
實現：dinic算法
 
*/ 
 
#include <iostream> 
//#define re(i, n) for(int i = 0; i < n; ++ i) 
using namespace std; 
 
const int nMax = 2505; 
const int INF = 0x7fffffff; 
int V[nMax]; 
int cnt; 
int queue[nMax], dis[nMax]; 
struct Edge 
{ 
    int v, w, next; 
    Edge(){} 
    Edge(int v, int w, int next):v(v), w(w), next(next){} 
}adj[8 * nMax]; 
int s, t; 
 
int min(int a, int b) 
{ 
    return a < b ? a : b; 
} 
 
void add(int u, int v, int w)//u - > v 
{ 
    adj[cnt] = Edge(v, w, V[u]); 
    V[u] = cnt ++; 
    adj[cnt] = Edge(u, 0, V[v]); 
    V[v] = cnt ++; 
} 
 
int bfs() 
{ 
    int front, rear; 
    int v; 
    memset(dis, 0, sizeof(dis)); 
    front = rear = 0; 
    dis[s] = 1; 
    queue[front ++] = s; 
    while(rear < front) 
    { 
        int u = queue[rear ++]; 
        for(int i = V[u]; i != -1; i = adj[i].next) 
            if(adj[i].w && dis[v = adj[i].v] == 0) 
            { 
                dis[v] = dis[u] + 1; 
                if(v == t) return 1; 
                queue[front ++] = v; 
            } 
    } 
    return 0; 
} 
 
int dfs(int u, int limit = INF) 
{ 
    if(u == t) return limit; 
    int count = 0; 
    for(int i = V[u]; i != -1; i = adj[i].next) 
    { 
        int v = adj[i].v; 
        if((dis[v] == dis[u] + 1) && adj[i].w) 
        { 
            int z = dfs(v, min(limit - count, adj[i].w)); 
            if(z > 0) 
            { 
                count += z; 
                adj[i].w -= z; 
                adj[i ^ 1].w += z;//改為adj[i + 1] += z  ， 會超時！ 
            } 
            else 
                dis[v] = -1; 
        } 
    } 
    return count; 
} 
 
int dinic() 
{ 
    int ans = 0; 
    while(bfs()) 
        ans += dfs(s); 
    return ans; 
} 
 
int main() 
{ 
    //freopen("f://data.in", "r", stdin); 
    int m, n; 
    int sum; 
    while(scanf("%d %d", &m, &n) != EOF) 
    { 
        cnt = 0; 
        int x; 
        sum = 0; 
        s = 0; 
        t = m * n + 1; 
        memset(V, -1, sizeof(V)); 
        for(int i = 1; i <= m; ++ i) 
            for(int j = 1; j <= n; ++ j) 
            { 
                scanf("%d", &x); 
                sum += x; 
                if((i + j) & 1) 
                { 
                    add(s, (i - 1) * n + j, x); 
                    //上 
                    if(i > 1) add((i - 1) * n + j, (i - 2) * n + j, INF); 
                    //下 
                    if(i < m) add((i - 1) * n + j, i * n + j, INF); 
                    //左 
                    if(j > 1) add((i - 1) * n + j, (i -1) * n + j - 1, INF); 
                    //右 
                    if(j < n) add((i - 1) * n + j, (i - 1) * n + j + 1, INF); 
                } 
                else 
                    add((i - 1) * n + j, t, x); 
            } 
        printf("%d\n",sum - dinic()); 
    } 
    return 0; 
} 
作者：lhshaoren