HDU2819

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

题目大意：

　　给出一个N*N的0/1矩阵，只能交换整行或者整列，问最少交换多少次可以变成一个主对角线上的数都为1的矩阵。

解题思路：

　　对行和列进行二分匹配，如果行和列之间不是完全匹配，直接输出 -1；否则就对匈牙利算法匹配后的得到的每一列对应的行进行操作（当然你也可以是对列进行操作，后面的交换也要进行相应的调整），如果行i不对应于列i，而行j对应列i，那么交换第i,j列。好题！

AC代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn=+;

 bool link[maxn][maxn],vis[maxn];

 int col[maxn];  //记录匈牙利算法跑完以后各列所匹配的行

 int N;

 pair<int,int> ans[maxn];

 bool finds(int x){

     for(int i=;i<=N;i++){

         if(link[x][i]&&!vis[i]){

             vis[i]=true;

             if(col[i]==||finds(col[i])){

                 col[i]=x;

                 return true;

             }

         }

     }

     return false;

 }

 int main(){

     int t;

     while(scanf("%d",&N)==){

         for(int i=;i<=N;i++){

             for(int j=;j<=N;j++){

                 scanf("%d",&t);

                 if(t)   link[i][j]=true;

                 else    link[i][j]=false;

             }

         }

         memset(col,false,sizeof(col));

         bool no=false;

         for(int i=;i<=N;i++){

             memset(vis,false,sizeof(vis));

             if(!finds(i)){

                 no=true;    break;

             }

         }

         if(no)  printf("-1\n");

         else{

             int cnt=;

             for(int i=;i<=N;i++){

                 if(col[i]==i)   continue;

                 else{

                     for(int j=i+;j<=N;j++){

                         if(col[j]==i){

                             ans[cnt]=make_pair(i,j);

                             col[j]=col[i];

                             cnt++;

                         }

                     }

                 }

             }

             printf("%d\n",cnt);

             for(int i=;i<cnt;i++){

                 printf("C %d %d\n",ans[i].first,ans[i].second);

             }

         }

     }

     return ;

 }

巴特西

HDU2819

最新文章

热门文章