首页 > ACM题库 > HDU-杭电 > HDU 3657-Game-网络流-[解题报告]HOJ
2014
11-30

HDU 3657-Game-网络流-[解题报告]HOJ

Game

问题描述 :

onmylove has invented a game on n × m grids. There is one positive integer on each grid. Now you can take the numbers from the grids to make your final score as high as possible. The way to get score is like
the following:
● At the beginning, the score is 0;
● If you take a number which equals to x, the score increase x;
● If there appears two neighboring empty grids after you taken the number, then the score should be decreased by 2(x&y). Here x and y are the values used to existed on these two grids. Please pay attention that "neighboring grids" means there exits and only exits one common border between these two grids.

Since onmylove thinks this problem is too easy, he adds one more rule:
● Before you start the game, you are given some positions and the numbers on these positions must be taken away.
Can you help onmylove to calculate: what’s the highest score onmylove can get in the game?

输入:

Multiple input cases. For each case, there are three integers n, m, k in a line.
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.

输出:

Multiple input cases. For each case, there are three integers n, m, k in a line.
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.

样例输入:

2 2 1
2 2
2 2
1 1
2 2 1
2 7
4 1
1 1

样例输出:

4
9

Hint
As to the second case in Sample Input, onmylove gan get the highest score when calulating like this: 2 + 7 + 4 - 2 × (2&4) - 2 × (2&7) = 13 - 2 × 0 - 2 × 2 = 9.

http://acm.hdu.edu.cn/showproblem.php?pid=3657

#include<iostream>
using namespace std;
#define N 2550
#define M 2000000
#define inf 0x7fffffff
struct Graph{    
    struct node{    
        int v,next,flow;    
        node(){}; 
        node(int a,int b,int c):next(a),v(b),flow(c){};    
    }E[M];    
    int pre[N];   
    int head[N];    
    int cur[N];  
    int dis[N];   
    int NV,NE;    
    int gap[N];  
    void init(int n){    
        memset(head,-1,sizeof(head));    
        NE=0;    
        NV=n;    
    }    
    void insert(int u,int v,int w){    
        E[NE]=node(head[u],v,w);    
        head[u]=NE++;    
        E[NE]=node(head[v],u,0);  
        head[v]=NE++;  
    }    
    int SAP(int s,int t){  
        memset(dis,0,sizeof(dis));  
        memset(gap,0,sizeof(gap));  
        for(int i=0;i<NV;i++)   
            cur[i]=head[i];  
        int u=pre[s]=s;  
        int maxflow=0,aug=INT_MAX;  
        gap[0]=NV;  
        while(dis[s]<NV){  
    loop:   for(int &i=cur[u];i!=-1;i=E[i].next){  
                int v=E[i].v;  
                if(E[i].flow&&dis[u]==dis[v]+1){  
                    if(aug>E[i].flow)  
                        aug=E[i].flow;  
                    pre[v]=u;  
                    u=v;  
                    if(v==t){  
                        maxflow+=aug;  
                        for(u=pre[u];v!=s;v=u,u=pre[u]){  
                            E[cur[u]].flow-=aug;  
                            E[cur[u]^1].flow+=aug;  
                        }  
                        aug=INT_MAX;  
                    }  
                    goto loop;  
                }  
            }  
            int mindis=NV;  
            for(int i=head[u];i!=-1;i=E[i].next){  
                int v=E[i].v;  
                if(E[i].flow&&mindis>dis[v]){  
                    cur[u]=i;  
                    mindis=dis[v];  
                }  
            }  
            if(--gap[dis[u]]==0)  
                break;  
            gap[dis[u]=mindis+1]++;  
            u=pre[u];  
        }  
        return maxflow;  
    }  
}G;
int map[55][55];
int main(void){
	int n,m,k;
	while(~scanf("%d%d%d",&n,&m,&k)){
		int beg=n*m+1,end=beg+1;
		G.init(end);
		int s=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				scanf("%d",&map[i][j]);
				s+=map[i][j];
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				int u=(i-1)*m+j;
				if((i+j)%2){
					G.insert(beg,u,map[i][j]);
					if(i>1) G.insert(u,u-m,2*(map[i][j]&map[i-1][j]));
					if(j>1) G.insert(u,u-1,2*(map[i][j]&map[i][j-1]));
					if(i<n) G.insert(u,u+m,2*(map[i][j]&map[i+1][j]));
					if(j<m) G.insert(u,u+1,2*(map[i][j]&map[i][j+1]));
				}
				else
					G.insert(u,end,map[i][j]);
			}
		while(k--){
			int x,y;
			scanf("%d%d",&x,&y);
			int u=(x-1)*m+y;
			if((x+y)%2){
				for(int i=G.head[beg];i!=-1;i=G.E[i].next)
					if(G.E[i].v==u){
						G.E[i].flow=inf;
						break;
					}
			}
			else{
				for(int i=G.head[u];i!=-1;i=G.E[i].next)
					if(G.E[i].v==end){
						G.E[i].flow=inf;
						break;
					}
			}
		}
		printf("%d\n",s-G.SAP(beg,end));
	}
}
			

在网上看到的一句话恍然大悟啊,建立一个最小割模型之后,假设x点与源点是连着的,说明你是把x点给取到手了,不连,说明你是把x点去除,之前一直不太明白边的容量是怎么来确定的,现在知道了,方格取数是相邻两个不能取,假设x,y是相邻的两点,他们直接建无穷大的边的原因就是:假设你最后把x,y都取来了,那么x和y的这条边就是一条割边,最小割是一定要把这条割边去掉的,去掉的代价就是该边的权值,试想如果这条边是无穷大的,程序会来割这条边吗?显然不会!所以这样就保证了x,y是不会同时被取到的。而这题相邻的可以取,只不过要额外的代价,还是假设x,y都取来了,那么这时候x,y边就是割边,程序会把它割掉,所以该边容量不是无穷大,而是相应的代价,至于后面的一定要取的几个点,只需要把他们和源点或汇点的容量设为无穷大,这样程序一定不会去割这条边,最后的结果就是这些点都留下来了,也就是都取了!

参考:http://blog.csdn.net/me4546/article/details/6662959


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法