首页 > ACM题库 > HDU-杭电 > HDU 4306-Mahjong-DFS-[解题报告]HOJ
2015
05-23

HDU 4306-Mahjong-DFS-[解题报告]HOJ

Mahjong

问题描述 :

In the 22nd Century, more than one hundred million people attend the Mahjong Sports all over the world. Professional Mahjong players are getting more and more attentions. In many high schools, there’ll be a large-scale Mahjong match every year to select talented students to attend the National Olympiad in Mahjong. For high scores to prove themselves and eager to be a professional Mahjong player someday, students compete with each other for the honor of the Mahjong.
Saki, a girl whose mother and elder sister are professional Mahjong players, will attend the National Olympiad in Mahjong in province (NOMP) this year. To beat other high school, achieve the first prize and attend the National Olympiad in Mahjong (NOM), she and her friends decide to make a camp to train their Mahjong skill.
A very important skill of Mahjong match is to control power of the game. A good Mahjong player could control the game, even all tiles of the game, just like Amae Koromo, whose favorite skill is "catching the moon from the bottom of the sea". This time, Saki and her friends are training their control skill of the Mahjong tiles via the following way.
Lightning

Saki got a lot of colored Mahjong tiles, and put them into an n * n matrix. Assume there are no more than two Mahjong tiles with the same color. Saki wants to use the Psychic force to control the tiles to the specified state. She could do two kinds of operation as follows:
A. To choose a row arbitrarily, and then swap two tiles’ position in this row. This operation will cost CA magic power.
B. To choose a column arbitrarily, and then swap two tiles’ position in this column. This operation will cost CB magic power.
Moreover, if you do the same kind of operation as you just did, the operation will cost no power. For example, Saki could make operation BAAAAA but just cost CB+CA magic power. Saki wants to know how to do the operations to finish the task with the least cost.

输入:

There are several cases.
The first line is an integer T (T < = 20), indicating the test cases.
Each case starts with three integers n, CA, CB, (1<=n<=300, 1<=CA, CB<=10^6). then 2*n*n integer follows, indicating the initial state and the target state of the grid. Each integer Aij(1<=Aij<=10^5) represent a Mahjong tile.

输出:

There are several cases.
The first line is an integer T (T < = 20), indicating the test cases.
Each case starts with three integers n, CA, CB, (1<=n<=300, 1<=CA, CB<=10^6). then 2*n*n integer follows, indicating the initial state and the target state of the grid. Each integer Aij(1<=Aij<=10^5) represent a Mahjong tile.

样例输入:

3
3 16 9
2 5 6
1 1 3
7 8 3
2 5 1
3 3 6
7 8 1
2 193 43
1 2
2 1
1 2
2 2
3 10 20
1 2 3
4 5 4
3 2 1
2 1 2
1 5 3
4 3 4

样例输出:

Case #1: 34
Case #2: Take off the shoes!
Case #3: 30

题意: 给定原矩阵和目标矩阵。http://acm.hdu.edu.cn/showproblem.php?pid=4306

两种操作: 选一横行的两元素交换(花费ca)。

选一列的两元素交换(cb)。

连续一个操作只花费一次。

问:从原矩阵到目标矩阵最小花费。

官方解法: 我就随便看看吧。

这道题目需要用2-sat解决,但要成功转化出模型需要一些巧妙的构造和基础图论知识的证明,最后还要注意一些细节。

首先,题目中的前三段可以直接无视(偶已经很体贴的用图隔开了不是么)。。

要解决这道题目,我们首先可以构造证明,一个状态经过最多三段操作(每段操作指若干次某种操作)之后可以到达任意状态。
我们不妨假设操作顺序为A…AB…BA…A(反之类似)。
原图中的一个格子坐标为(x0,y0),要转移到目标的坐标为(x1,y1),则显然最后一段操作之前坐标为(x1,y2).
依次类推,它的转移路径应该为:(x0,y0)—>(x0,y2)—>(x1,y2)—>(x1,y1),则唯一影响路径的是y2。
那么这种构造方式能否成功就取决于从(x0,y2)是否能转换到(x1,y2)。
换言之,就是我们第一段操作需要使每一列各点所要到达的x1互不相等。
再换言之,如果我们以每个点的原始位置集x0到其目标位置集x1构建二分图,则如果能够找到n个不相交的完美匹配就构造成功了。
显然每行有n个点,则x集每个点的度都是n;同理y集每个点的度也是n。
对于x集的任意子集S,其在y集中的相邻集记作A(S),显然S的度为n|S|,而其邻集A(S)的度至少为n|S|。
由于每个点的度数都相同为n,则显然|A(S)|>=|S|,该图一定存在完美匹配。
将该匹配删掉之后,每个点的度数依然相等,同理可证我们可以找到下一组匹配。则我们可以证明上文的结论。

有了上面的证明,我们可以根据情况进行分类讨论。
1.不能达到
2.直接等同
3.一步可达
4.两步可达
5.三步可达

前三种都可以直接判断,后两种我们只要可以判断一种就知道不满足其他四种的就是最后一种。注意每种判断都需要行列各做一次。
我们考虑怎么判断两步可达的状态,不妨先考虑A…AB…B的操作(反之同理)。
每个点(x0,y0)要到达目标点(x1,y1),显然路径为(x0,y0)—>(x0,y1)—>(x1,y1)。
由于每种点最多出现两次,则每种点可选的中转点方案最多两组。
当某两种点的某种方案需要的中转点之间出现交集的时候,说明二者方案不能同时选择。
那么这是经典的2-sat问题,可以用强联通分量或者染色解决。

具体的实现上应该有一些技巧,偶的标程实现方法过于naive了,跑了2s….QAQ。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 305;
const int MAXM = 100010;

struct Edge
{
    int v, next;
} shift[MAXN*MAXN*2], edge[MAXN*MAXN*4];
int shiftNumber, edgeNumber;
int shiftHead[MAXN*MAXN*2], edgeHead[MAXN*MAXN*2];

int a[MAXN][MAXN], b[MAXN][MAXN];
int al[MAXN*MAXN], bl[MAXN*MAXN];
int ta[MAXN], tb[MAXN];
int na[MAXM], nb[MAXM];
int pa[MAXM][2], pb[MAXM][2];
bool va[MAXM], vb[MAXM];
int n, nn, ca, cb;
int differ[MAXN*MAXN], differNumber;
int maxNumber;

bool inStack[MAXN*MAXN*2];
int dfn[MAXN*MAXN*2], low[MAXN*MAXN*2];
int stack[MAXN*MAXN*2], belong[MAXN*MAXN*2];
int top, index, componentNumber;

inline int min(int x, int y)
{
    return x < y ? x : y;
}

inline int max(int x, int y)
{
    return x > y ? x : y;
}

inline void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

inline int getPosition(int x, int y)
{
    return x * n + y;
}

inline int getRow(int pos)
{
    return pos / n;
}

inline int getColumn(int pos)
{
    return pos % n;
}

void clearEdges()
{
    shiftNumber = 0;
    edgeNumber = 0;
    memset(shiftHead, -1, sizeof(shiftHead));
    memset(edgeHead, -1, sizeof(edgeHead));
}

inline void addShift(int u, int v)
{
    shift[shiftNumber].v = v;
    shift[shiftNumber].next = shiftHead[u];
    shiftHead[u] = shiftNumber ++;
}

inline void addEdge(int u, int v)
{
    edge[edgeNumber].v = v;
    edge[edgeNumber].next = edgeHead[u];
    edgeHead[u] = edgeNumber ++;
}

void transpose()
{
    for(int i=0; i<n; ++i)
    {
        for(int j=i+1; j<n; ++j)
        {
            swap(a[i][j], a[j][i]);
            swap(b[i][j], b[j][i]);
        }
    }
}

void getDifference()
{
    differ[al[0]] = 0;
    differNumber = 1;
    for(int i=1; i<nn; ++i)
    {
        if(al[i] != al[i-1])
        {
            differ[al[i]] = differNumber ++;
        }
    }
}

void getNumberPosition()
{
    memset(na, 0, sizeof(na));
    memset(nb, 0, sizeof(nb));
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            pa[a[i][j]][na[a[i][j]]++] = getPosition(i, j);
            pb[b[i][j]][nb[b[i][j]]++] = getPosition(i, j);
        }
    }

}

bool isUnreachable()
{
    sort(al, al + nn);
    sort(bl, bl + nn);
    for(int i=0; i<nn; ++i)
    {
        if(al[i] != bl[i])
        {
            return true;
        }
    }
    return false;
}

bool isReachableByOneStep()
{
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            ta[j] = a[i][j];
            tb[j] = b[i][j];
        }
        sort(ta, ta + n);
        sort(tb, tb + n);
        for(int j=0; j<n; ++j)
        {
            if(ta[j] != tb[j])
            {
                return false;
            }
        }
    }
    return true;
}

int myStack[MAXN * MAXN * 8];
int myStackTop;

void push(int x)
{
    myStack[myStackTop ++] = x;
}

int pop()
{
    return myStack[-- myStackTop];
}

bool isEmpty()
{
    return myStackTop == 0;
}

void dfs(int x, int depth)
{
    int i, t;
    myStackTop = 0;
start:
    dfn[x] = low[x] = index ++;
    inStack[x] = true;
    stack[top++] = x;
    for(i=edgeHead[x]; i!=-1; i=edge[i].next)
    {
        if(dfn[edge[i].v] == -1)
        {
            push(x);
            push(depth);
            push(i);
            push(t);
            x = edge[i].v;
            depth = depth + 1;
            goto start;
ret:
            low[x] = min(low[x], low[edge[i].v]);
        }
        else if(inStack[edge[i].v])
        {
            low[x] = min(low[x] ,dfn[edge[i].v]);
        }
    }
    if(dfn[x] == low[x])
    {
        do
        {
            t = stack[--top];
            inStack[t] = false;
            belong[t] = componentNumber;
        }
        while(t != x);
        ++ componentNumber;
    }
    if(isEmpty())
    {
        return;
    }
    t = pop();
    i = pop();
    depth = pop();
    x = pop();
    goto ret;
}

void tarjan()
{
    memset(inStack, false, sizeof(inStack));
    memset(dfn, -1, sizeof(dfn));
    memset(low, -1, sizeof(low));
    top = index = componentNumber = 0;
    for(int i=0; i<differNumber*2; ++i)
    {
        if(dfn[i] == -1)
        {
            dfs(i, 0);
        }
    }
}

bool isReachableByTwoStep()
{
    clearEdges();
    for(int i=1; i<=maxNumber; ++i)
    {
        if(na[i] == 1)
        {
            addShift(getPosition(getRow(pa[i][0]), getColumn(pb[i][0])), differ[i]<<1);
            addShift(getPosition(getRow(pa[i][0]), getColumn(pb[i][0])), (differ[i]<<1) + 1);
        }
        else if(na[i] == 2)
        {
            addShift(getPosition(getRow(pa[i][0]), getColumn(pb[i][1])), differ[i]<<1);
            addShift(getPosition(getRow(pa[i][0]), getColumn(pb[i][0])), (differ[i]<<1) + 1);
            addShift(getPosition(getRow(pa[i][1]), getColumn(pb[i][0])), differ[i]<<1);
            addShift(getPosition(getRow(pa[i][1]), getColumn(pb[i][1])), (differ[i]<<1) + 1);
        }
    }
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            for(int k=shiftHead[getPosition(i, j)]; k!=-1; k=shift[k].next)
            {
                for(int l=shift[k].next; l!=-1; l=shift[l].next)
                {
                    if((shift[k].v ^ 1) == shift[l].v)
                    {
                        continue;
                    }
                    addEdge(shift[k].v, shift[l].v ^ 1);
                    addEdge(shift[l].v, shift[k].v ^ 1);
                }
            }
        }
    }
    tarjan();
    for(int i=0; i<differNumber; ++i)
    {
        if(belong[i<<1] == belong[(i<<1)+1])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int caseNumber;
    scanf("%d", &caseNumber);
    for(int cas=1; cas<=caseNumber; ++cas)
    {
        scanf("%d%d%d", &n, &ca, &cb);
        nn = n * n;
        bool isSame = true;
        maxNumber = 0;
        for(int i=0,k=0; i<n; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                scanf("%d", &a[i][j]);
                al[k++] = a[i][j];
                maxNumber = max(maxNumber, a[i][j]);
            }
        }
        for(int i=0,k=0; i<n; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                scanf("%d", &b[i][j]);
                bl[k++] = b[i][j];
                if(a[i][j] != b[i][j])
                {
                    isSame = false;
                }
            }
        }
        printf("Case #%d: ", cas);
        if(isSame)
        {
            printf("0\n");
        }
        else
        {
            if(isUnreachable())
            {
                printf("Take off the shoes!\n");
            }
            else
            {
                int ans = min(ca * 2 + cb, cb * 2 + ca);
                if(isReachableByOneStep())
                {
                    ans = ca;
                }
                transpose();
                if(ans > cb)
                {
                    if(isReachableByOneStep())
                    {
                        ans = cb;
                    }
                }
                if(ans > ca + cb)
                {
                    getDifference();
                    getNumberPosition();
                    if(isReachableByTwoStep())
                    {
                        ans = ca + cb;
                    }
                    else
                    {
                        transpose();
                        getNumberPosition();
                        if(isReachableByTwoStep())
                        {
                            ans = ca + cb;
                        }
                    }
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

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

参考:http://blog.csdn.net/julyana_lin/article/details/8069181