方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3086 Accepted Submission(s): 1182
Problem Description
给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
Input
包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例,输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
Author
ailyanlu
Source
Recommend
8600
1,EK:(邻接表建图)
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=30; const int EM=30000; const int INF=0x3f3f3f3f; int n; int map[VM][VM],g[1010][1010],pre[1010]; struct Edge{ int u,v,nxt; int cap; }edge[EM]; int src,des; int EK(){ int maxflow=0; while(1){ memset(pre,-1,sizeof(pre)); queue<int> q; while(!q.empty()) q.pop(); int tmp=INF; q.push(src); while(!q.empty()){ int cur=q.front(); q.pop(); for(int i=1;i<=n*n+1;i++){ if(g[cur][i]!=0 && pre[i]==-1){ tmp=min(tmp,g[cur][i]); pre[i]=cur; q.push(i); } } if(pre[des]!=-1) break; } if(pre[des]==-1) break; int u=des; while(u!=src){ g[pre[u]][u]-=tmp; g[u][pre[u]]+=tmp; u=pre[u]; } maxflow+=tmp; } return maxflow; } int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n)){ memset(g,0,sizeof(g)); int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&map[i][j]); sum+=map[i][j]; } src=0,des=n*n+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if((i+j)%2==0) g[src][(i-1)*n+j]=map[i][j]; //addedge(src,(i-1)*n+j,map[i][j]); else g[(i-1)*n+j][des]=map[i][j]; //addedge((i-1)*n+j,des,map[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<4;k++){ int x=i+dir[k][0]; int y=j+dir[k][1]; if(x>=1 && x<=n && y>=1 && y<=n && (i+j)%2==0) g[(i-1)*n+j][(x-1)*n+y]=INF; //addedge((i-1)*n+j,(x-1)*n+j,INF); } printf("%d\n",sum-EK()); } return 0; }
2,非邻接表建图:头脑不清楚了,,有空再写吧
相关推荐
蟠桃记 1 折线分割平面 2 不容易系列之一 2 骨牌铺方格 3 不容易系列之(3)—— LELE的RPG难题 3 Children’s Queue 3 献给杭电五十周年校庆的礼物 3 钥匙计数之二 3 钥匙计数之一 3 母牛的故事 3 超级楼梯 3 不容易...
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类