/*
题解:
因为这个数据比较大,所以用动态规划会超时。
将图转换成黑白棋盘问题,i + j 为奇数的与s节点相连,边的权值为棋盘上对应位置的值,其他的与t节点相连,边的权值为棋盘上对应位置的值,然后让棋盘上相邻之间的节点用边相连,边的权值为INF。这样问题就转换为了最大点权独立集问题。
定理:
1、最大点权独立集 = sum - 最小点权覆盖集。
2、最小点权覆盖集 = 最小割 = 最大流
实现:dinic算法
参见:
http://wenku.baidu.com/view/98deaf06b52acfc789ebc91a.html###
http://www.cnblogs.com/ltang/archive/2010/11/17/1879573.html
*/
#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 queue[nMax];//建立层次图时使用到的队列
int 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 V[nMax];//V[u]表示起点为u的第一条边,与Edge结合使用,从而实现邻接表的效果
int cnt;
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)//与u相连的边
if(adj[i].w && dis[v = adj[i].v] == 0)//可通行并且 v 之间没有被访问过
{
dis[v] = dis[u] + 1;
if(v == t) return 1;
queue[front ++] = v;
}
}
return 0;
}
int dfs(int u, int limit = INF)//返回从u出发到t,增广路经的最小边
{
if(u == t) return limit;
int count = 0;
for(int i = V[u]; i != -1; i = adj[i].next)//与u 相连的边
{
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)//增广路经的最小边不为0,即v到t可通行
{
count += z;
adj[i].w -= z;
adj[i ^ 1].w += z;//改为adj[i + 1] += z , 会超时!
}
else
dis[v] = -1;//效果等同于删除与v相关的所有边
}
}
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;
}
分享到:
相关推荐
骨牌铺方格 3 不容易系列之(3)—— LELE的RPG难题 3 Children’s Queue 3 献给杭电五十周年校庆的礼物 3 钥匙计数之二 3 钥匙计数之一 3 母牛的故事 3 超级楼梯 3 不容易系列之二 3 一只小蜜蜂... 3 阿牛的EOF牛肉串...
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
杭电ACMhdu1163
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
Least Common Multiple ...先利用gcd算法求两个数的最大公约数,再考虑最小公倍数=两数乘积/最大公约数,即可求得最小公倍数。 注意:要考虑到输入的输入的n个数中的0,有0的要去掉0求其他数的最小公倍数。 代码:
hdu题目分类