HDU 2819 Swap

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2819

解题思路：

这道题是要把n×n的矩阵的对角线全部变为一。

然后我们把纵坐标，横坐标分别为二分图的左右两个集合，如果要对角线全部为1。

首先要满足的条件是：

这个二分图的最大匹配数，必须为N，如果小于肯定不能满足题意。换句话说每一个列都必须和一个行有匹配。

然后进行交换就行了。

实现代码：

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

const int MAXN=105;
int g[MAXN][MAXN],used[MAXN];
int linker[MAXN];
int N;
int a[MAXN*10],b[MAXN*10];

bool dfs(int u){
    for(int i=1;i<=N;i++){
        if(!used[i]&&g[u][i]){
            used[i]=1;
            if(linker[i]==-1||dfs(linker[i])){
                linker[i]=u;
                return true;
            }
        }
    }
    return false;
}

int hungry(){
    memset(linker,-1,sizeof(linker));
    int res=0;

    for(int i=1;i<=N;i++){
        memset(used,0,sizeof(used));
        if(dfs(i))
            res++;
    }
    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]);

        int ans=hungry();
        if(ans<N){
            printf("-1
");
            continue;
        }

        int res=0;
        int i,j;
            for(i=1;i<=N;i++){
                
                //第i列要和和与第i行匹配的列相交换。
                for(j=i;j<=N;j++)
                    if(linker[j]==i)
                        break;
                if(i!=j){
                    a[res]=i;b[res++]=j;
                    swap(linker[i],linker[j]);
                }
            }

         printf("%d
",res);
        for(i=0;i<res;i++)
            printf("C %d %d
",a[i],b[i]);
        }

    }