题目：Swap
总结：只需要交换行或者只交换列就可以了，二分图的左别存放行，右边放与行相连的列。然后用匈牙利算法求一下最大匹配数，如果与n相等，就说明可以交换得到。否则就是不能，然后再根据pre算出要交换的行
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> using namespace std; const int N = 105; vector<int>G[N]; int g[N][N],n; int vis[N],pre[N],a[N]; bool dfs(int u){ for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(!vis[v]){ vis[v] = 1; if(!pre[v] || dfs(pre[v])){ pre[v] = u; return true; } } } return false; } void solve(){ int b[1005][2]; int ans = 0; memset(pre,0,sizeof pre); for(int i = 1;i <= n;i++){ G[i].clear(); for(int j = 1;j <= n;j++){ if(g[i][j]){ G[i].push_back(j); } } } for(int i = 1;i <= n;i++){ memset(vis,0,sizeof vis); if(dfs(i)){ ans++; } } if(ans != n){ printf("-1\n"); return; } for(int i = 1;i <= n;i++){ a[pre[i]] = i; } ans = 0; for(int i = 1;i <= n;i++){ if(a[i] != i){ for(int j = i+1;j <= n;j++){ if(a[j] == i){ swap(a[i],a[j]); // printf("R %d %d\n",i,j); b[ans][0] = i; b[ans++][1] = j; break; } } } // printf("%d ",pre[i]); } printf("%d\n",ans); for(int i = 0;i < ans;i++){ printf("R %d %d\n",b[i][0],b[i][1]); } } int main(){ while(~scanf("%d",&n)){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ scanf("%d",&g[i][j]); } } solve(); } return 0; } /* 4 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 */