首页 > 代码库 > 【wikioi】1907 方格取数3(最大流+最大权闭合子图)
【wikioi】1907 方格取数3(最大流+最大权闭合子图)
这题我一开始想到的是状压,看到n<=30果断放弃。
然后也想到了黑白染色,然后脑残了,没想到怎么连边。
很简单的一题
黑白染色后,每个点向四周连边,容量为oo,然后如果是黑(白)节点,源连一条边,容量为权值;如果是白(黑)节点,连一条边到汇,容量为权值。
最后答案为所有格子权值和-最大流(其实是最小割)
ps:(其实就是之前做过的qq农场 囧。。http://www.cnblogs.com/iwtwiioi/p/3893519.html
为什么这样做参考我以前写的博文(http://www.cnblogs.com/iwtwiioi/p/3872099.html)
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=1000, M=N<<4, oo=~0u>>1;struct ED { int u, v, next, cap; } e[M];int n, m, cnt=1;int d[N], gap[N], cur[N], p[N], ihead[N];inline int id(const int &x, const int &y) { return (x-1)*m+y; }inline void add(const int &u, const int &v, const int &c) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].v=v; e[cnt].u=u; e[cnt].cap=c; e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].v=u; e[cnt].u=v; e[cnt].cap=0;}int isap(const int &s, const int &t, const int &n) { int ret=0, f, u, v, i; for1(i, 0, n) cur[i]=ihead[i]; gap[0]=n; u=s; while(d[s]<n) { for(i=cur[u]; i; i=e[i].next) if(e[i].cap && d[u]==d[e[i].v]+1) break; if(i) { v=e[i].v; p[v]=cur[u]=i; u=v; if(u==t) { for(f=oo; u!=s; u=e[p[u]].u) f=min(f, e[p[u]].cap); for(u=t; u!=s; u=e[p[u]].u) e[p[u]].cap-=f, e[p[u]^1].cap+=f; ret+=f; } } else { if(! (--gap[d[u]]) ) break; d[u]=n; cur[u]=ihead[u]; for(i=ihead[u]; i; i=e[i].next) if(e[i].cap && d[u]>d[e[i].v]+1) d[u]=d[e[i].v]+1; ++gap[d[u]]; if(u!=s) u=e[p[u]].u; } } return ret;}int main() { read(n); read(m); int ans=0, t, now, S=id(n, m)+1, T=id(n, m)+2; for1(i, 1, n) for1(j, 1, m) { read(t); ans+=t; now=id(i, j); if((i+j)%2) add(S, now, t); else add(now, T, t); if(j<m) add(now, now+1, oo), add(now+1, now, oo); if(i<n) add(now, id(i+1, j), oo), add(id(i+1, j), now, oo); } print(ans-isap(S, T, T)); return 0;}
题目描述 Description
«问题描述:
在一个有m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任
意2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务:
对于给定的方格棋盘,按照取数要求编程找出总和最大的数。
输入描述 Input Description
第1 行有2 个正整数m和n,分别表示棋盘的行数
和列数。接下来的m行,每行有n个正整数,表示棋盘方格中的数。
输出描述 Output Description
将取数的最大总和输出
样例输入 Sample Input
3 3
1 2 3
3 2 3
2 3 1
样例输出 Sample Output
11
数据范围及提示 Data Size & Hint
n,m<=30
【wikioi】1907 方格取数3(最大流+最大权闭合子图)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。