HDU 2819 点击打开链接
大致题意：
有一个n*n的矩阵，这n*n个数要么是0，要么是1。
现在问你，是否能通过一系列操作(行与行交换，列与列交换)使得操作之后的矩阵的主对角线全为1。
大致思路：
我们将x坐标和y坐标分成两个集合，如果（x，y）的位置上是1，就将x和y进行连边。那么，就构成了一个二分图。如果这个二分图的最大匹配是n的话，那么代表这个矩阵可以进行变换使得主对角线全为1。如果不是n的话，那么就不能了。。。
最后我们要输出交换的路径，那我们从第一行开始遍历，如果第i行匹配的值不是第i列（主对角线的x和y当然相等了），那我们就再次遍历寻找哪行匹配的是第i列。假如，我们找到第k行匹配的是第i列，那我们就将i和k进行交换，注意，交换之后我们要将他们的匹配值也要交换，因为操作是再上一次操作之后进行的。。。
代码：
#include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<iostream> using namespace std; int pre[200]; int vis[200]; int ml[200],mr[200]; int one[200],two[200]; vector<int>V[200]; int n; int MaxMatch()//匈牙利算法bfs实现 { int sum=0; memset(vis,0,sizeof(vis)); memset(ml,-1,sizeof(ml)); memset(mr,-1,sizeof(mr)); for(int i=1; i<=n; i++) { if(ml[i]==-1) { queue<int>Q; Q.push(i); pre[i]=-1; int flag=0; while(!Q.empty()&&!flag) { int st=Q.front(); Q.pop(); for(int j=0; j<V[st].size()&&!flag; j++) { int to=V[st][j]; if(vis[to]!=i) { vis[to]=i; Q.push(mr[to]); if(mr[to]>=0) { pre[mr[to]]=st; } else { flag=1; int d=st,e=to; while(d!=-1) { int temp=ml[d]; ml[d]=e; mr[e]=d; d=pre[d]; e=temp; } } } } } if(flag)sum++; } } return sum; } int main() { while(~scanf("%d",&n)) { int a; for(int i=0;i<=n;i++) { V[i].clear(); } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { scanf("%d",&a); if(a)V[i].push_back(j); } } int ans=MaxMatch(); if(ans<n) { printf("-1\n"); } else { int num=0;//记录操作数 for(int i=1; i<=n; i++) { if(ml[i]!=i)//第i行对应的不是第i列 { for(int j=1; j<=n; j++)//遍历寻找匹配值是第i列的那行 { if(ml[j]==i)//找到了 { one[num]=i;//记录要交换的行 two[num]=j; num++;//操作数加1 int temp=ml[j];//将他们的匹配值进行交换 ml[j]=ml[i]; ml[i]=temp; } } } } printf("%d\n",num); for(int i=0; i<num; i++) { printf("R %d %d\n",one[i],two[i]); } } } }
