HDU 2819

题目链接：https://cn.vjudge.net/problem/HDU-2819

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?

InputThere 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.OutputFor each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.
Sample Input

Sample Output

1
R 1 2
-1

题意：

给出一个N*N的01矩阵，要求你通过一些行交换或者列交换使得矩阵的主对角线上全为1；

题解：

不难想象，进行行列缩点，如果某个位置a_ij等于1，就往二分图中加入一条边( i , j )，如果求出最大匹配等于N，说明可以通过行列的变换得到目标矩阵；

然后根据匹配情况，输出相应的交换步骤即可；

AC代码：

#include<bits/stdc++.h>
#define MAX 103
#define INF 0x3f3f3f3f
using namespace std;
int n,matrix[MAX][MAX];

struct Hopcroft_Karp{
    int edge[MAX][MAX],Mx[MAX],My[MAX],Nx,Ny;
    int dx[MAX],dy[MAX],dis;
    bool vis[MAX];
    void init(int uN,int vN)
    {
        Nx=uN, Ny=vN;
        for(int i=1;i<=uN;i++) for(int j=1;j<=vN;j++) edge[i][j]=0;
    }
    void addedge(int u,int v){edge[u][v]=1;}
    bool searchP()
    {
        queue<int> Q;
        dis=INF;
        memset(dx,-1,sizeof(dx));
        memset(dy,-1,sizeof(dy));
        for(int i=1;i<=Nx;i++)
        {
            if(Mx[i]==-1)
            {
                Q.push(i);
                dx[i]=0;
            }
        }
        while(!Q.empty())
        {
            int u=Q.front();Q.pop();
            if(dx[u]>dis) break;
            for(int v=1;v<=Ny;v++)
            {
                if(edge[u][v] && dy[v]==-1)
                {
                    dy[v]=dx[u]+1;
                    if(My[v]==-1) dis=dy[v];
                    else
                    {
                        dx[My[v]]=dy[v]+1;
                        Q.push(My[v]);
                    }
                }
            }
        }
        return dis!=INF;
    }
    bool dfs(int u)
    {
        for(int v=1;v<=Ny;v++)
        {
            if(!vis[v] && edge[u][v] && dy[v]==dx[u]+1)
            {
                vis[v]=1;
                if(My[v]!=-1 && dy[v]==dis) continue;
                if(My[v]==-1 || dfs(My[v]))
                {
                    My[v]=u;
                    Mx[u]=v;
                    return true;
                }
            }
        }
        return false;
    }
    int max_match()
    {
        int ret=0;
        memset(Mx,-1,sizeof(Mx));
        memset(My,-1,sizeof(My));
        while(searchP())
        {
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=Nx;i++) if(Mx[i]==-1 && dfs(i)) ret++;
        }
        return ret;
    }
}HK;

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        HK.init(n,n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&matrix[i][j]);
                if(matrix[i][j]) HK.addedge(i,j);
            }
        }

        int max_match=HK.max_match();
        if(max_match==n)
        {
            queue< pair<int,int> > output;
            for(int j=1;j<=n;j++)
            {
                int u1=j, u2=HK.My[j];
                int v1=j, v2=HK.Mx[j];
                if(u1!=u2)
                {
                    output.push(make_pair(u1,u2));
                    HK.My[v1]=u1, HK.My[v2]=u2;
                    HK.Mx[u1]=v1, HK.Mx[u2]=v2;
                }
            }

            printf("%d
",output.size());
            while(!output.empty())
            {
                printf("R %d %d
",output.front().first,output.front().second);
                swap(matrix[output.front().first],matrix[output.front().second]);
                output.pop();
            }
        }
        else printf("-1
");
    }
}

PS.刚开始还以为HK算法的模板出错了，吓死了……

PS.注意更改匹配情况时，match数组的变更；