HOJ 2713 Matrix1

Matrix1

My Tags	(Edit)

	Source : Classical Problem
	Time limit : 5 sec		Memory limit : 64 M

Submitted : 424, Accepted : 129

Lilu0355 is a thoughtful boy and always plays a classical mathematic game.The game plays like that, there is a n * m matrix, each grid of this matrix is filled with a non-negative number. You should remove some numbers from the matrix and make sure that any two numbers removed are not adjacent in the matrix. What is the biggest sum of those removed numbers? Lilu can always find the answer, can you?

Input

The first line is a integer T indicating the number of test cases.T cases fllows. Each case includs two integers n, m(m ≤ 50,n ≤ 50) and n * m non-negative integers, which is not more than 40000.

Output

For each test case, output the biggest sum.

Sample Input

Sample Output

题意：

给出一张n*m的网格图，每个格子有一个非负权值c[i][j]，选取一些两两不相邻的格子，使得权值最大...

分析：

最大权值独立集问题，网格图，所以可以黑白染色，S向黑色点连一条容量为格子权值的边，白色点向T连一条容量为格子权值的边，黑色点向相邻的白色点连一条容量为+∞的边，然后求出的最小割就是最小点权覆盖，用总权值减去最小割就是答案了...

代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 //by NeighThorn
 6 #define inf 0x3f3f3f3f
 7 using namespace std;
 8 
 9 const int maxn=2500+2+5,maxm=maxn*5+5;
10 
11 int cas,n,m,mv[4][2]={0,1,0,-1,1,0,-1,0},ans;
12 int S,T,cnt,hd[maxn],fl[maxm],to[maxm],nxt[maxm],pos[maxn];
13 
14 inline void add(int s,int x,int y){
15     fl[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
16     fl[cnt]=0;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;
17 }
18 
19 inline bool bfs(void){
20     memset(pos,-1,sizeof(pos));
21     int q[maxn],head=0,tail=0;
22     q[0]=S,pos[S]=0;
23     while(head<=tail){
24         int top=q[head++];
25         for(int i=hd[top];i!=-1;i=nxt[i])
26             if(pos[to[i]]==-1&&fl[i])
27                 pos[to[i]]=pos[top]+1,q[++tail]=to[i];
28     }
29     return pos[T]!=-1;
30 }
31 
32 inline int find(int v,int f){
33     if(v==T)
34         return f;
35     int res=0,t;
36     for(int i=hd[v];i!=-1&&f>res;i=nxt[i])
37         if(pos[to[i]]==pos[v]+1&&fl[i])
38             t=find(to[i],min(f-res,fl[i])),res+=t,fl[i]-=t,fl[i^1]+=t;
39     if(!res)
40         pos[v]=-1;
41     return res;
42 }
43 
44 inline int dinic(void){
45     int res=0,t;
46     while(bfs())
47         while(t=find(S,inf))
48             res+=t;
49     return res;
50 }
51 
52 signed main(void){
53     scanf("%d",&cas);
54     while(cas--){
55         memset(hd,-1,sizeof(hd));
56         cnt=ans=0;scanf("%d%d",&n,&m);S=0,T=n*m+1;
57         for(int i=1;i<=n;i++)
58             for(int j=1,x;j<=m;j++){
59                 scanf("%d",&x);ans+=x;
60                 if((i+j)&1){
61                     add(x,S,(i-1)*m+j);
62                     for(int k=0;k<4;k++){
63                         int xx=i+mv[k][0],yy=j+mv[k][1];
64                         if(xx>0&&xx<=n&&yy>0&&yy<=m)
65                             add(inf,(i-1)*m+j,(xx-1)*m+yy);
66                     }
67                 }
68                 else
69                     add(x,(i-1)*m+j,T);
70             }
71         ans=ans-dinic();printf("%d
",ans);
72     }
73     return 0;
74 }

View Code

by NeighThorn