HDU2819 Swap 看似很难的题目其实用二分匹配就解决了
还是转载了别人的分析，这道题目我做的时候看到过的人很少，自己害怕了，还好自己在做二分匹配的专题，就用二分匹配的想法去想，结果做出来了，unbelivevable！！！
接下来是分析：
转自 http://blog.csdn.net/hackbuteer1/article/details/7398008
这个博主的做法建图方式有些独特比较难懂，我还是常规建图
其实就是简单的二分匹配，行和列匹配就可以了，关键是点不在于匹配而在于排序，因为匹配后的match存储的是列的匹配对象，所以只需要把列从小到大(或者从大到小，因为是special judge，所以主、副对角线都是一样)排序，每排序一次就保存当前交换了的下标，注意这里不能用冒泡而最好用选择，因为题目要求len不能大于1000，,这里纠结了一下，郁闷死了)
其次要明确：只交换行或者只交换列都是可以换出来的，这个动动脑子想一下也可以明白的。二分图左边的节点为每一行的行号，二分图右边的节点为每一行中出现的“1”对应的列号，这样用匈牙利算法就可以匹配了。
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[1212];int mp[1212][1212];int marry[1212];bool vis[1212];int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m,k;struct Node{int x,y;}node[1212];void clear(){memset(marry,-1,sizeof(marry));memset(node,0,sizeof(node));memset(mp,0,sizeof(mp));for(int i=0;i<1012;i++)G[i].clear();}bool dfs(int x){for(int i=1;i<=n;i++){if(mp[x][i] && !vis[i]){vis[i]=true;if(marry[i]==-1 || dfs(marry[i])){marry[i]=x;return 1;}}}return 0;}int main(void){while(cin>>n){clear();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j];}}int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}if(ans!=n)puts("-1");else//排序，耐心点就好了，可以统一为只换行或者只换列，不必要行列都换，比较麻烦，能通过行列变换的肯定可以只通过单一的行变换或者列变换{int cnt=0;for(int i=1;i<n;i++){if(marry[i]!=i){for(int j=i+1;j<=n;j++){if(i==marry[j]){marry[j]=marry[i];marry[i]=i;node[cnt].x=i;node[cnt].y=j;cnt++;}}}}printf("%d\n",cnt);for(int i=0;i<cnt;i++){printf("C %d %d\n",node[i].x,node[i].y);}}}}