首页 > 代码库 > 方格取数(2)
方格取数(2)
hdu1569:http://acm.hdu.edu.cn/showproblem.php?pid=1569
题意：中文题。
题解：经典的问题。首先，按照(i+j)%2==1和(i+j)%2==0把所有的点分成两部分x，y两部分。分别对于x，和y部分来说，任何取两个数都是不相邻的，所以可以任意去。现在的问题x中取多少个数，y中选取多少个数，是的最终的和最大。所以接下来，如果i,j相邻，则i，j之间建立一边，容量是无穷大。x部分和源点建立一边，y部分与汇点建立一边。这样跑网络流，跑出来的流量就是最大流，也就是最小割，再结合一下最小割的定义，很明显，最终的答案就是总的和-maxflow。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<queue> 6 #define INF 100000000 7 using namespace std; 8 const int N=2612; 9 const int M=14820; 10 struct Node{ 11 int v; 12 int f; 13 int next; 14 }edge[M]; 15 int n,m,u,v,cnt,sx,ex; 16 int head[N],pre[N]; 17 int mp[51][51];//根据题目要求申请 18 void init(){ 19 cnt=0; 20 memset(head,-1,sizeof(head)); 21 } 22 void add(int u,int v,int w){ 23 edge[cnt].v=v; 24 edge[cnt].f=w; 25 edge[cnt].next=head[u]; 26 head[u]=cnt++; 27 edge[cnt].f=0; 28 edge[cnt].v=u; 29 edge[cnt].next=head[v]; 30 head[v]=cnt++; 31 } 32 bool BFS(){ 33 memset(pre,0,sizeof(pre)); 34 pre[sx]=1; 35 queue<int>Q; 36 Q.push(sx); 37 while(!Q.empty()){ 38 int d=Q.front(); 39 Q.pop(); 40 for(int i=head[d];i!=-1;i=edge[i].next ){ 41 if(edge[i].f&&!pre[edge[i].v]){ 42 pre[edge[i].v]=pre[d]+1; 43 Q.push(edge[i].v); 44 } 45 } 46 } 47 return pre[ex]>0; 48 } 49 int dinic(int flow,int ps){ 50 int f=flow; 51 if(ps==ex)return f; 52 for(int i=head[ps];i!=-1;i=edge[i].next){ 53 if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 54 int a=edge[i].f; 55 int t=dinic(min(a,flow),edge[i].v); 56 edge[i].f-=t; 57 edge[i^1].f+=t; 58 flow-=t; 59 if(flow<=0)break; 60 } 61 62 } 63 if(f-flow<=0)pre[ps]=-1; 64 return f-flow; 65 } 66 int solve(){ 67 int sum=0; 68 while(BFS()) 69 sum+=dinic(INF,sx); 70 return sum; 71 } 72 int main() { 73 int sum=0; 74 while(~scanf("%d%d",&n,&m)){ 75 init();sum=0; 76 for(int i=1;i<=n;i++){ 77 for(int j=1;j<=m;j++){ 78 scanf("%d",&mp[i][j]); 79 sum+=mp[i][j]; 80 if((i+j)%2==0){ 81 add(0,(i-1)*m+j,mp[i][j]); 82 } 83 else{ 84 add((i-1)*m+j,n*m+1,mp[i][j]); 85 } 86 } 87 } 88 for(int i=1;i<=n;i++){ 89 for(int j=1;j<=m;j++){ 90 if((i+j)%2==0){ 91 int a=(i-1)*m+j; 92 if(i>1)add(a,a-m,INF); 93 if(i<n)add(a,a+m,INF); 94 if(j>1)add(a,a-1,INF); 95 if(j<m)add(a,a+1,INF); 96 } 97 } 98 } 99 sx=0,ex=n*m+1;100 printf("%d\n",sum-solve());101 }102 return 0;103 }
方格取数(2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。