当前位置:编程学习 > C/C++ >>

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) *
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,