php做网站要多久,一个网站空间可以做多少个网站,网络营销为导向的企业网站,设计得很好的企业网站Description 在一个有m*n 个方格的棋盘中#xff0c;每个方格中有一个正整数。现要从方格中取数#xff0c;使任意2 个数所在方格没有公共边#xff0c;且取出的数的总和最大。试设计一个满足要求的取数算法。 Input 第1 行有2 个正整数m和n#xff0c;分别表示棋盘的行数和…Description 在一个有m*n 个方格的棋盘中每个方格中有一个正整数。现要从方格中取数使任意2 个数所在方格没有公共边且取出的数的总和最大。试设计一个满足要求的取数算法。 Input 第1 行有2 个正整数m和n分别表示棋盘的行数和列数。接下来的m行每行有n个正整数表示棋盘方格中的数。 Output 对于给定的方格棋盘按照取数要求编程找出总和最大的数将取数的最大总和输出。 Sample Input 3 31 2 33 2 32 3 1 Sample Output 11 HINT n,m30 嗯......这道题大概算是自己想出来的第一道网络流的题吧 虽然想了很久WA了很多发但终于A掉了...... 网络流的题真是难想(但这一题还是比较简单的)如果不是我已经知道这道题要用网络流做还不知道要想到什么时候去了...... 好了不扯多了进正题 首先我们发现直接建模的话非常不好搞体重的条件不好表示...... 于是我们就想是否可以把我们选完数之后剩下的数给表示出来呢我们发现这个不难做到。只需将棋盘黑白二染色把黑点、白点各看成一块相邻的格子间有边相连不难发现将黑白两块分开的割的方案就是不选的点的合法方案脑补一下应该可以搞出来。所以最小割即是合法方案中选出的点和最大的方案。于是我们可以从源点向所有黑(白)点连一条容量为这个格子里的数的边从黑(白)点向相邻的点连一条容量为INF的边再从白(黑)点向汇点连一条容量为当前格子里的数的边跑一边最大流即可得出不选的点的最小和用所有数字之和减去它就是答案。 update:其实这就是最大独立集等于总点数减去最大匹配数 下面贴代码 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecmath6 #define maxm 1000107 #define INF (125)8 #define r(j) (j^1)9
10 using namespace std;
11 typedef long long llg;
12
13 int head[101*101],next[maxm],to[maxm],c[maxm],tt1;
14 int a[101][101],zx[4]{0,0,1,-1},zy[4]{1,-1,0,0};
15 int d[maxm],l,r,dep[maxm],ans,tut,s,t,n,m;
16
17 int getint(){
18 int w0;bool q0;
19 char cgetchar();
20 while((c9||c0)c!-) cgetchar();
21 if(c-) q1,cgetchar();
22 while(c0c9) ww*10c-0,cgetchar();
23 return q?-w:w;
24 }
25
26 void link(int x,int y,int z){
27 to[tt]y;next[tt]head[x];head[x]tt;
28 to[tt]x;next[tt]head[y];head[y]tt;
29 c[tt^1]z;
30 }
31
32 bool bfs(){
33 for(int i1;it;i) dep[i]0;
34 lr0;d[r]s;dep[s]1;int u;
35 while(l!r){
36 ud[l];
37 for(int ihead[u];i;inext[i])
38 if(!dep[to[i]] c[i]0){
39 dep[to[i]]dep[u]1;
40 d[r]to[i];
41 }
42 }
43 return dep[t]0;
44 }
45
46 int dfs(int u,int low){
47 int res0,v;
48 if(ut) return low;
49 if(!low) return 0;
50 for(int ihead[u];i;inext[i])
51 if(c[i]0 dep[to[i]]dep[u]1){
52 vdfs(to[i],min(low-res,c[i]));
53 c[i]-v;c[r(i)]v;resv;
54 }
55 return res;
56 }
57
58 int main(){
59 freopen(a.in,r,stdin);
60 freopen(a.out,w,stdout);
61 ngetint();mgetint();sn*m1;ts1;
62 for(int i1;in;i)
63 for(int j1;jm;j)
64 a[i][j]getint();
65 for(int i1,now(0);in;i)
66 for(int j1;jm;j){
67 now;
68 if(!((ij)1)){
69 link(s,now,a[i][j]);
70 for(int k0,x,y,n1;k4;k){
71 xizx[k];yjzy[k];
72 if(x0 xn y0 ym){
73 n1(x-1)*my;
74 link(now,n1,INF);
75 }
76 }
77 }
78 else link(now,t,a[i][j]);
79 tuta[i][j];
80 }
81 while(bfs())
82 while(int totdfs(s,INF)) anstot;
83 printf(%d\n,tut-ans);
84 return 0;
85 } 转载于:https://www.cnblogs.com/lcf-2000/p/5551356.html
