首页 > ACM题库 > HDU-杭电 > HDU 3865-A Hard Journey-图-[解题报告]HOJ
2015
04-13

HDU 3865-A Hard Journey-图-[解题报告]HOJ

A Hard Journey

问题描述 :

ChenX was taken away by the arch devil, so the sharp shooter Brother Zheng was going to rescue him. The enemy’s army was distributed in an N * N grid, and each grid also can be divided in M * M small grids.

Brother Zheng’s army has two kinds of attack form : from top to bottom, or from left to right. The weapon they use is Break-Cloud arrow, so each arrow will cost P fighting strength to eliminate a row or a column enemies in a big grid.

Notice that they can change the attack form at any time, and when they once change their attack form, they will use Q fighting strength.

The initial position of Brother Zheng is at the top-left corner, and ChenX was locked by arch devil at the right-bottom corner. When once make a move, Brother Zheng should eliminate all the enemies in the current big grid. If the current attack form is from top to bottom, then they can move onto the right grid of the big grid; if the current attack form is from left to right, then they can move onto the bottom grid of the big grid. The initial attack form can be either of the two.

Now Brother Zheng want to know how much the least fighting strength is so that can rescue ChenX.

For the case as the followed picture, N = 2, M = 3, P = 2, Q = 1.
Brother Zheng choices to start with the attack form: from top to bottom. It takes P * 1 fighting strength to eliminate all the enemies at grid[1][1]. Then Brother Zheng changed attack form to “from left to right” using Q fighting strength, and moved to the bottom grid[2][1]. To eliminate all the enemies, it takes P * 2 fighting strength. Then Brother Zheng changed attack form to ”from top to bottom” using Q fighting strength, and moved to the right grid[2][2], after used P * 3 fighting strength to eliminate this grid, ChenX was rescue with P * 1 + Q + P * 2 + Q + P * 3 = 14 fighting strength.

D_num

输入:

For each case, the first line contains 4 integers: N, M, P, Q(0 < N <= 20, 0 < M <= 15, 0 <= P <= 20, 0 <= Q <= 20), the next N * N blocks, each block contains M * M matrixes, rows first.

输出:

For each case, the first line contains 4 integers: N, M, P, Q(0 < N <= 20, 0 < M <= 15, 0 <= P <= 20, 0 <= Q <= 20), the next N * N blocks, each block contains M * M matrixes, rows first.

样例输入:

2 3 2 1
0 0 1
0 0 1
0 0 1
1 1 1
1 1 1
1 1 1
0 1 1
0 0 0
1 1 1
1 0 0
0 1 0
0 0 1
1 3 3 1
0 0 1
0 0 1
1 1 1

样例输出:

14
7

/**
我的做法是这样的:这题有n*n个大格子,每个大格子里面有m*m个小格子。每个大格子里的走法有3种情况,分别为全部从上往下、全部从左往右、一部分上到下一部分左到右,我们可以先对每一个大格子预处理一下,求出这3种走法消耗的能量值。对于第3种走法,我们可以用最小点覆盖求出最小消耗。然后对于所有的大格子,DP求解最优值。状态分为两种,一种是消灭完改格子的敌人之后方向向右,一种是向下,状态转移的时候需要注意。表达能力欠佳,,,还是发代码吧。。。

**/

#include <iostream>
#include <cstring>

#include <cstdio>

#include <algorithm>

using
namespace std;

int cost[25][25][5];
int
dp[25][25][3];
int
g[25][25];
int
n, m, p, q;

const int N = 35;
const
int M = N * N * 6;

struct Edge
{

    int v;
    Edge *next;
};

int
ne;
Edge
ebuf[M];        //内存池
Edge
*head[N];    //邻接表
void
addEdge(int from, int to)
{

    Edge &e = ebuf[ne++];
    e.v = to;
    e.next = head[from];
    head[from] = &e;
}

int cx[N], cy[N], disx[N], disy[N];    //cx[] cy[]:顶标; disx[] disy[]层次图标号
int
nx, ny;
int
Q[N];
bool
bfs()    //bfs找层次图
{

    memset(disx, 0, sizeof(disx));
    memset(disy, 0, sizeof(disy));
    bool flag = false;
    int l = 0, r = 0;
    for (int i = 1; i <= nx; i++)
        if (cx[i] ==  - 1)
            Q[r++] = i;
    while (l < r)
    {
        int x = Q[l++];
        for (Edge *p = head[x]; p; p = p->next)
        {
            int y = p->v;
            if (!disy[y])
            {
                disy[y] = disx[x] + 1;
                if (cy[y] ==  - 1)
                    flag = true;
                else
                {
                    disx[cy[y]] = disy[y] + 1;
                    Q[r++] = cy[y];
                }
            }
        }
    }
    return flag;
}

bool dfs(int x)
{

    for (Edge *p = head[x]; p; p = p->next)
    {
        int y = p->v;
        if (disy[y] == disx[x] + 1)    //在层次图中增广
        {
            disy[y] = 0;
            if (cy[y] ==  - 1 || dfs(cy[y]))
            {
                cx[x] = y;
                cy[y] = x;
                return true;
            }
        }
    }
    return false;
}

inline int HopcroftKarp()
{

    memset(cx,  -1, sizeof(cx));
    memset(cy,  -1, sizeof(cy));
    int ret = 0;
    while (bfs())
        for (int i = 1; i <= nx; i++)
            if (cx[i] ==  -1 && dfs(i))
                ret++;
    return ret;
}

int
hang[25];
int
lie[25];
void
cal_val(int g[25][25], int x, int y)
{

    memset(hang, 0, sizeof(hang));
    memset(lie, 0, sizeof(lie));
    memset(head, 0, sizeof(head));
    ne = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j])
            {
                addEdge(i, j);
                hang[i]++;
                lie[j]++;
            }
        }
    cost[x][y][1] = cost[x][y][2] = 0;
    for (int i = 1; i <= m; i++)
    {
        if (hang[i]) cost[x][y][1] += p;
        if (lie[i]) cost[x][y][2] += p;
    }
    nx = ny = m;
    cost[x][y][3] = cost[x][y][4] = HopcroftKarp() * p + q;
}

const int inf = 1000000005;

inline void Min(int &a, int b)
{

    if (b < a) a = b;
}

int main()
{

    //freopen(“in.txt”, “r”, stdin);

    while (scanf(“%d%d%d%d”, &n, &m, &p, &q) != EOF)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                for (int k = 1; k <= m; k++)
                    for (int h = 1; h <= m; h++)
                        scanf(“%d”, &g[k][h]);
                cal_val(g, i, j);
            }
        // dp
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 1; k <= 2; k++)
                    dp[i][j][k] = inf;
        dp[1][1][1] = min(cost[1][1][1], cost[1][1][4]);
        dp[1][1][2] = min(cost[1][1][2], cost[1][1][3]);

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i == 1 && j == 1)
                    continue;
                // top -> down
                Min(dp[i][j][1], dp[i - 1][j][1] + cost[i][j][1]);
                Min(dp[i][j][1], dp[i - 1][j][1] + cost[i][j][4] + q);
                Min(dp[i][j][1], dp[i - 1][j][2] + cost[i][j][1] + q);
                Min(dp[i][j][1], dp[i - 1][j][2] + cost[i][j][4] + q + q);

                Min(dp[i][j][2], dp[i - 1][j][1] + cost[i][j][2] + q);
                Min(dp[i][j][2], dp[i - 1][j][1] + cost[i][j][3]);
                Min(dp[i][j][2], dp[i - 1][j][2] + cost[i][j][2] + q + q);
                Min(dp[i][j][2], dp[i - 1][j][2] + cost[i][j][3] + q);

                // left -> right
                Min(dp[i][j][1], dp[i][j - 1][1] + cost[i][j][1] + q + q);
                Min(dp[i][j][1], dp[i][j - 1][1] + cost[i][j][4] + q);
                Min(dp[i][j][1], dp[i][j - 1][2] + cost[i][j][1] + q);
                Min(dp[i][j][1], dp[i][j - 1][2] + cost[i][j][4]);

                Min(dp[i][j][2], dp[i][j - 1][1] + cost[i][j][2] + q);
                Min(dp[i][j][2], dp[i][j - 1][1] + cost[i][j][3] + q + q);
                Min(dp[i][j][2], dp[i][j - 1][2] + cost[i][j][2]);
                Min(dp[i][j][2], dp[i][j - 1][2] + cost[i][j][3] + q);
            }
        int ans = min(dp[n][n][1], dp[n][n][2]);
        cout << ans << endl;
    }
}

参考:http:[email protected]/blog/static/172217863201162091511907/


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。