首页 > 代码库 > 【网络流24题----09】方格取数问题
【网络流24题----09】方格取数问题
«问题描述：
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
«数据输入：
由文件grid.in提供输入数据。文件第1 行有2 个正整数m和n，分别表示棋盘的行数
和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。
«结果输出:
程序运行结束时，将取数的最大总和输出到文件grid.out中。
输入文件示例 输出文件示例
grid.in
3 3
1 2 3
3 2 3
2 3 1
grid.out
11
(1<=N,M<=30)
对于棋盘黑白染色构出一张二分图，二分图最大独立集。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 910 10 #define inf 0x7fffffff 11 #define llg int 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,e[maxn],N,p[10][5],g[50][50],k,tot,se[50][50]; 14 15 struct DINIC 16 { 17 vector<llg>a[maxn],ba[maxn],val[maxn]; 18 llg dl[maxn],deep[maxn],bj[maxn]; 19 20 void insert(llg x,llg y,llg z) 21 { 22 a[x].push_back(y),val[x].push_back(z); 23 a[y].push_back(x),val[y].push_back(0); 24 ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1); 25 } 26 27 llg dfs(llg x,llg low) 28 { 29 llg va=0,inc=0; 30 if (x==N) return low; 31 llg w=a[x].size(); 32 for (llg i=0;i<w;i++) 33 if (deep[x]+1==deep[a[x][i]] && val[x][i]>0 && (va=dfs(a[x][i],min(low,val[x][i])))) 34 { 35 val[x][i]-=va; val[a[x][i]][ba[x][i]]+=va; inc+=va; 36 return va; 37 } 38 if (!inc) deep[x]=-1; 39 return 0; 40 } 41 42 void fencen() 43 { 44 llg x,w,v; deep[0]=0; 45 memset(bj,0,sizeof(bj)); 46 llg head=0,tail=1; dl[1]=0; bj[0]=1; 47 do 48 { 49 x=dl[++head]; w=a[x].size(); 50 for (llg i=0;i<w;i++) 51 { 52 v=a[x][i]; 53 if (bj[v] || val[x][i]<=0) continue; 54 dl[++tail]=v; 55 deep[v]=deep[x]+1; bj[v]=1; 56 } 57 }while (head!=tail); 58 } 59 60 llg dinic() 61 { 62 llg ans=0; 63 while (1) 64 { 65 fencen(); 66 if (!bj[N]) break; 67 ans+=dfs(0,inf); 68 } 69 return ans; 70 } 71 72 void oupt() 73 { 74 for (llg i=1;i<=k;i++) 75 { 76 printf("%d: ",i); 77 llg w=a[i].size(); 78 for (llg e=0;e<w;e++) 79 { 80 llg v=a[i][e]; 81 if (v>k && v<N && val[i][e]==0) printf("%d ",v-k); 82 } 83 printf("\n"); 84 } 85 } 86 }G; 87 88 llg ma(llg x,llg y) {return x*m-m+y;} 89 90 void init() 91 { 92 p[1][1]=1,p[2][1]=-1,p[3][2]=1,p[4][2]=-1; 93 cin>>n>>m; 94 N=n*m+1; 95 for (llg i=1;i<=n;i++) 96 for (llg j=1;j<=m;j++) 97 scanf("%d",&g[i][j]),tot+=g[i][j]; 98 for (llg i=1;i<=n;i++) 99 for (llg j=1;j<=m;j++)100 {101 for (llg k=1;k<=4;k++)102 {103 llg x=i+p[k][1],y=j+p[k][2];104 if (x>n || x<1 || y>m || y<1) continue;105 se[x][y]=(se[i][j]+1)%2;106 }107 }108 for (llg i=1;i<=n;i++)109 for (llg j=1;j<=m;j++)110 if (se[i][j])111 {112 for (llg k=1;k<=4;k++)113 {114 llg x=i+p[k][1],y=j+p[k][2];115 if (x>n || x<1 || y>m || y<1) continue;116 G.insert(ma(i,j),ma(x,y),inf);117 }118 G.insert(0,ma(i,j),g[i][j]);119 }120 for (llg i=1;i<=n;i++)121 for (llg j=1;j<=m;j++)122 if (!se[i][j])123 G.insert(ma(i,j),N,g[i][j]);124 }125 126 int main()127 {128 yyj("grid");129 init();130 cout<<tot-G.dinic();131 return 0;132 }
【网络流24题----09】方格取数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。