hdu2819Swap 匈牙利算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2819

//对于n*n矩阵的n行，我们要求每行都要有一个特别的1与其匹配，如果匹配数少于n，则输出-1
//二分图的构造方法是 第i行的第j列有一个1，那就在ij之间连一条边，则map[i][j]=1（后来发现其实跟构造矩阵相同。。） 
//如果匹配数为n，就对link进行排序，由于行变换和列变换相同，我们只进行行变换（为了能对应题目的实例） 
//假如是行在左边，该行上1所在的列在右边的话，那最终匹配后会得出link[j]=i，我们按照link的值排序 

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

int n,x;
bool map[105][105]; 
bool vis[105];
int link[105];

bool dfs(int t){
    for(int i=1;i<=n;i++)
    {
        if(map[t][i] && !vis[i])
        {
            vis[i]=1;
            if(link[i]==-1 || dfs(link[i]))
            {
                link[i]=t;
                return 1;
            }
        }
    }
    return 0;
}

int main(){
    
    while(cin>>n){
        memset(map,0,sizeof(map));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>map[i][j];
        
        memset(link,-1,sizeof(link));
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(!dfs(i))
            {
                flag=0;
                printf("-1
");
                break;
            }
        }
        
        if(flag){//选择排序 
            int tmp,m,i,k,mn,ans=0;
            int swap1[105],swap2[105];
            
            for(i=1;i<n;i++)
            {
                m=10000;
                for(k=i;k<=n;k++)
                    if(link[k]<m)
                    {
                        m=link[k];
                        mn=k;
                    }          
                if(i!=mn){
                    tmp=link[i];
                    link[i]=link[mn];
                    link[mn]=tmp;
                    swap1[ans]=i;swap2[ans++]=mn;
                }
            }
            printf("%d
",ans);
            for (int i=0;i<ans;i++)
                    printf("C %d %d
", swap1[i], swap2[i]);
        }    
    }
    return 0;
}
/*
4
1 0 0 0 
0 0 1 0
0 0 0 1
0 1 0 0

4
1 0 1 0 
0 0 1 0
0 0 1 1
0 1 0 1

5
1 0 1 0 0
0 0 1 0 0
0 0 1 1 1
0 1 0 1 0
*/