首页 > 搜索 > DFS搜索 > HDU 2819-Swap-分治-[解题报告]HOJ
2014
02-17

HDU 2819-Swap-分治-[解题报告]HOJ

Swap

问题描述 :

Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?

输入:

There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.

输出:

There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.

样例输入:

2
0 1
1 0
2
1 0
1 0

样例输出:

1
R 1 2
-1

题目大意就是给出一个矩阵,每个格子里面要么是0, 要么是1;是否能够经过交换(交换行或者列)使得主对角线上都是1。

其实就行和列的匹配,左边是行,右边是列,然后如果行列交点是1,那么就可以匹配,看是否为完美匹配,然后输出怎么交换的。开始很蒙的,后来仔细去想,可以这样理解,想要对角线上都是1,那么我们就可以锁定行,来选择列和它匹配,将选择的列移动到和该行形成对角线上是1的位置,比如和第一行匹配的列,就要移动要第一列,第二行的,就到第二列。其实就是对第i行,找一个第i个数是1的列和它匹配,然后看是否是最大匹配!

至于要输出路径,那么就应该想到是排序的时候交换路径,也就是说将cy里面的值,也就是列对应的行,从小到大排序,这个过程中交换的次数和交换的列,就是要输出的。这里要求交换次数不能超过1000,使用选择排序,交换次数最多是N!

那么存不存在只交换列不能解决,而行列交换一起进行就能解决的情况呢?也就是说我们要证明这个的正确性。其实如果交换行的话,无非是把‘1’的位置放到对角线上,使得某一行和某一列匹配,那么反过来也可以说是这一列和这一行匹配,其实是一样的。

做完这道题,我的感悟就是,只是一定要灵活运用,要会思考,不进算法要理解准确,同时应用,以及分析问题同样十分重要

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
int n, g[N][N], cx[N], cy[N], ans1[N*2], ans2[N*2];
bool used[N];

bool dfs( int u ) 
{
    for ( int i = 1; i <= n; ++i ) if ( g[u][i] && !used[i] ) {
        used[i] = true;
        if ( cy[i] == -1 || dfs( cy[i] ) ) {
            cy[i] = u;
            cx[u] = i;
            return true;
        }
    }
    return false;
}
int match()
{
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for ( int i = 1; i <= n; ++i ){
        memset( used, 0, sizeof(used));
        if ( dfs(i) ) res++;
        else break;
    }
    return res;
}
int main()
{
    while ( scanf("%d", &n) != EOF ) {
        for ( int i = 1; i <= n; ++i )
            for ( int j = 1; j <= n; ++j ) scanf("%d", &g[i][j]);
        if ( match() != n ) {
            printf("-1\n");
            continue;
        }
        int len = 0;
        for ( int i = 1; i <= n; ++i ) {
            int mark = i, tmp;
            for ( int j = i; j <= n; ++j ) 
                if ( cy[mark] > cy[j] ) mark = j;
            if ( mark == i ) continue;
            ans1[++len] = i, ans2[len] = mark;
            tmp = cy[mark];
            cy[mark] = cy[i];
            cy[i] = tmp;
        }
        printf("%d\n", len);
        for ( int i = 1; i <= len; ++i ) printf("C %d %d\n", ans1[i], ans2[i]);
    }
}

解题参考:http://blog.csdn.net/ac_lion/article/details/8887637


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮