首页 > ACM题库 > HDU-杭电 > HDU 3820-Golden Eggs-DFS-[解题报告]HOJ
2015
04-13

HDU 3820-Golden Eggs-DFS-[解题报告]HOJ

Golden Eggs

问题描述 :

There is a grid with N rows and M columns. In each cell you can choose to put a golden or silver egg in it, or just leave it empty. If you put an egg in the cell, you will get some points which depends on the color of the egg. But for every pair of adjacent eggs with the same color, you lose G points if there are golden and lose S points otherwise. Two eggs are adjacent if and only if there are in the two cells which share an edge. Try to make your points as high as possible.

输入:

The first line contains an integer T indicating the number of test cases.
There are four integers N, M, G and S in the first line of each test case. Then 2*N lines follows, each line contains M integers. The j-th integer of the i-th line Aij indicates the points you will get if there is a golden egg in the cell(i,j). The j-th integer of the (i+N)-th line Bij indicates the points you will get if there is a silver egg in the cell(i,j).

Technical Specification
1. 1 <= T <= 20
2. 1 <= N,M <= 50
3. 1 <= G,S <= 10000
4. 1 <= Aij,Bij <= 10000

输出:

The first line contains an integer T indicating the number of test cases.
There are four integers N, M, G and S in the first line of each test case. Then 2*N lines follows, each line contains M integers. The j-th integer of the i-th line Aij indicates the points you will get if there is a golden egg in the cell(i,j). The j-th integer of the (i+N)-th line Bij indicates the points you will get if there is a silver egg in the cell(i,j).

Technical Specification
1. 1 <= T <= 20
2. 1 <= N,M <= 50
3. 1 <= G,S <= 10000
4. 1 <= Aij,Bij <= 10000

样例输入:

2
2 2 100 100
1 1
5 1
1 4
1 1
1 4 85 95
100 100 10 10
10 10 100 100

样例输出:

Case 1: 9
Case 2: 225

这道题挺难的,在网上见到这段分析:

对原矩阵黑白染色
1 2 3
4 5 6
7 8 9
A={1,3,5,7,9}
B={2,4,6,8}
矩阵中每个点可以取两个值中的任意一个,或者都不取。
根据这一个条件,我们可以把一个点拆分成两部分,k,k’。
对A集合中的点,k为金蛋,k’为银蛋。
B集合中的点,k为银蛋,k’为金蛋。
k->k’连一条容量为inf的边,这样就可以保证k,k’只取其中一个,或者都不取。
从S到k,从k’到T 分别连一条容量为其价值的边。
对A中的金蛋k,向B中的金蛋k’连一条容量为G的边。
对B中的银蛋k,向A中的银蛋k’连一条容量为S的边。
总的价值减去最小割,就是要求的价值。
这样建图的原因跟上两题类似。自己思考思考吧。

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define maxn 6000
#define INF 100000
int A[55][55],B[55][55],Count[55][55];
struct Edge
{
	int from, to, cap, flow;
};

int n, m, s, t;
vector<Edge> edges;    // 边数的两倍
vector<int> G[maxn];   // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn];        // BFS使用
int d[maxn];           // 从起点到i的距离
int cur[maxn];         // 当前弧指针
int min(int a,int b)
{
	if(a<b) return a;
	else return b;
}
void AddEdge(int from, int to, int cap)
{
	int len;
	Edge temp;
	temp.from=from;temp.to=to;temp.cap=cap;temp.flow=0;
	edges.push_back(temp);
	temp.from=to;temp.to=from;temp.cap=0;temp.flow=0;
    edges.push_back(temp);
    len = edges.size();
    G[from].push_back(len-2);
    G[to].push_back(len-1);
}
bool BFS()
{
	memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty())
	{
		int x = Q.front(); Q.pop();
		for(int i = 0; i < G[x].size(); i++)
		{
			Edge& e = edges[G[x][i]];
			if(!vis[e.to] && e.cap > e.flow)
			{
				vis[e.to] = 1;
				d[e.to] = d[x] + 1;
				Q.push(e.to);
			}
		}
    }
    return vis[t];
}
int DFS(int x, int a)
{
	if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++)
	{
		Edge& e = edges[G[x][i]];
		if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0)
		{
			e.flow += f;
			edges[G[x][i]^1].flow -= f;
			flow += f;
			a -= f;
			if(a == 0) break;
		}
    }
    return flow;
}
int Maxflow()
{
    int flow = 0;
    while(BFS())
	{
		memset(cur, 0, sizeof(cur));
		flow += DFS(s, INF);
    }
    return flow;
}
int main()
{
    int T;
    int gold,silver;
    int i,j;
    scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        cas++;
        int tot=0;
        int now=0;
        scanf("%d%d%d%d",&n,&m,&gold,&silver);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&A[i][j]);
                tot+=A[i][j];
                Count[i][j] = ++now;
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&B[i][j]);
                tot+=B[i][j];
            }
        s=0;t=2*n*m+1;
        for(i=0;i<=t;i++) G[i].clear();
        for(i=1;i<=n*m;i++) AddEdge(i,i+n*m,INF);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i+j)%2==0)
                {
                    AddEdge(s,Count[i][j],A[i][j]);
                    AddEdge(n*m+Count[i][j],t,B[i][j]);
                    if(i-1>0) AddEdge(Count[i][j],n*m+Count[i-1][j],gold);
                    if(i+1<=n) AddEdge(Count[i][j],n*m+Count[i+1][j],gold);
                    if(j-1>0) AddEdge(Count[i][j],n*m+Count[i][j-1],gold);
                    if(j+1<=m) AddEdge(Count[i][j],n*m+Count[i][j+1],gold);
                }
                else
                {
                    AddEdge(s,Count[i][j],B[i][j]);
                    AddEdge(n*m+Count[i][j],t,A[i][j]);
                    if(i-1>0) AddEdge(Count[i][j],n*m+Count[i-1][j],silver);
                    if(i+1<=n) AddEdge(Count[i][j],n*m+Count[i+1][j],silver);
                    if(j-1>0) AddEdge(Count[i][j],n*m+Count[i][j-1],silver);
                    if(j+1<=m) AddEdge(Count[i][j],n*m+Count[i][j+1],silver);
                }
            }
        printf("Case %d: %d\n",cas,tot-Maxflow());
    }
    return 0;
}

 

 

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/kidgin7439/article/details/23855777


, ,