把网站做二维码,咸宁商城网站建设,古楼角网站建设,南京十大广告公司HDU 1565 方格取数(1)给你一个n*n的格子的棋盘#xff0c;每个格子里面有一个非负数。从中取出若干个数#xff0c;使得任意的两个数所在的格子没有公共边#xff0c;就是说所取的数所在的2个格子不能相邻#xff0c;并且取出的数的和最大。 Input 包括多个测试实例#… HDU 1565 方格取数(1) 给你一个n*n的格子的棋盘每个格子里面有一个非负数。从中取出若干个数使得任意的两个数所在的格子没有公共边就是说所取的数所在的2个格子不能相邻并且取出的数的和最大。 Input 包括多个测试实例每个测试实例包括一个整数n 和n*n个非负数(n20) Output 对于每个测试实例输出可能取得的最大的和 Sample Input 3
75 15 21
75 15 28
34 70 5 Sample Output 188直接用这个程序拿双倍经验吧~ 1 #include iostream2 #include cstring3 #include cstdio4 #include queue5 6 using namespace std;7 const int INF2147483647;8 const int maxn10010,maxm1000010;9 int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn];10 int map[53][53];11 void addedge(int a,int b,int c)12 {13 nxt[cnt]fir[a];14 to[cnt]b;15 cap[cnt]c;16 fir[a]cnt;17 }18 19 bool BFS(int S,int T)20 {21 memset(dis,0,sizeof(dis));22 dis[T]1;23 queueintq;q.push(T);24 while(!q.empty())25 {26 int nodeq.front();q.pop();27 for(int ifir[node];i;inxt[i])28 {29 if(dis[to[i]])continue;30 dis[to[i]]dis[node]1;31 q.push(to[i]);32 }33 }34 return dis[S];35 }36 int fron[maxn];37 int ISAP(int S,int T)38 {39 if(!BFS(S,T))40 return 0;41 for(int i1;iT;i)gap[dis[i]];42 int pS,ret0;43 memcpy(fron,fir,sizeof(fir));44 while(dis[S]T)45 {46 if(pT){47 int fINF;48 while(p!S){49 fmin(f,cap[path[p]]);50 pto[path[p]^1];51 }52 pT;retf;53 while(p!S){54 cap[path[p]]-f;55 cap[path[p]^1]f;56 pto[path[p]^1];57 }58 }59 int iifron[p];60 for(;ii;iinxt[ii]){61 if(!cap[ii]||dis[to[ii]]1!dis[p])62 continue;63 else 64 break;65 }66 if(ii){67 pto[ii];68 path[p]ii;69 }70 else{71 if(--gap[dis[p]]0)break;72 int minnT1;73 for(int ifir[p];i;inxt[i])74 if(cap[i])75 minnmin(minn,dis[to[i]]);76 gap[dis[p]minn1];77 fron[p]fir[p];78 if(p!S)79 pto[path[p]^1]; 80 }81 }82 return ret;83 }84 85 void Init()86 {87 memset(fir,0,sizeof(fir));88 memset(gap,0,sizeof(gap)); 89 cnt1;90 }91 92 int n,m;93 94 int dot(int x,int y){95 return (x-1)*my;96 }97 98 int main()99 {
100 int sum;
101 while(~scanf(%d%d,n,m))
102 {
103 Init();sum0;
104 for(int i1;in;i)
105 for(int j1;jm;j){
106 scanf(%d,map[i][j]);
107 summap[i][j];
108 }
109
110 for(int i1;in;i)
111 for(int j1;jm;j)
112 if((ij)%21){
113 addedge(0,(i-1)*mj,map[i][j]);
114 addedge((i-1)*mj,0,0);
115 }
116
117 for(int i1;in;i)
118 for(int j1;jm;j)
119 if((ij)%20){
120 addedge((i-1)*mj,n*m1,map[i][j]);
121 addedge(n*m1,(i-1)*mj,0);
122 }
123
124 for(int i1;in;i)
125 for(int j1;jm;j)
126 if((ij)%21){
127 if(i1n){
128 addedge(dot(i,j),dot(i1,j),INF);
129 addedge(dot(i1,j),dot(i,j),0);
130 }
131 if(i-11){
132 addedge(dot(i,j),dot(i-1,j),INF);
133 addedge(dot(i-1,j),dot(i,j),0);
134 }if(j-11){
135 addedge(dot(i,j),dot(i,j-1),INF);
136 addedge(dot(i,j-1),dot(i,j),0);
137 }
138 if(j1m){
139 addedge(dot(i,j),dot(i,j1),INF);
140 addedge(dot(i,j1),dot(i,j),0);
141 }
142
143 }
144 printf(%d\n,sum-ISAP(0,n*m1));
145 }
146 return 0;
147 } 转载于:https://www.cnblogs.com/TenderRun/p/5224864.html
