这题的目的是，通过一系列交换，让矩阵中A[i, i] (1 <= i <= N)的值全为1。
首先要明确：
如果某行或者某列全是0。那怎么换都没办法的。
否则，一定能换出来。
这个动动脑子想一下可以明白的。
其次要明确：只交换行或者只交换列都是可以换出来的。
这个动动脑子想一下也可以明白的。
明确了这两点，这问题就变成了二分图的匹配问题。
二分图左边的节点为每一行的行号
二分图右边的节点为每一行中出现的“1”对应的列号
这样用匈牙利算法就可以匹配了。
#include <stdio.h>
#include <string.h>
#define NR 128
int N;
int mat[NR][NR];
int res[NR];
char vis[NR];
int dfs(int i)
{
int j;
for (j = 1; j <= N; j++) {
if (mat[i][j] && !vis[j]) {
vis[j] = 1;
if (!res[j] || dfs(res[j])) {
res[j] = i;
return 1;
}
}
}
return 0;
}
int solve()
{
int i, j, k, c, t, m;
static int a[NR], b[NR];
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
scanf("%d", &mat[i][j]);
memset(res, 0, sizeof(res));
for (i = 1; i <= N; i++) {
memset(vis, 0, sizeof(vis));
if (!dfs(i))
return 0;
}
c = 0;
for (j = 1; j <= N; j++) {
m = j;
for (k = j; k <= N; k++)
if (res[k] <= res[m])
m = k;
if (m != j) {
a[c] = m;
b[c] = j;
c++;
t = res[m];
res[m] = res[j];
res[j] = t;
}
}
printf("%d\n", c);
for (i = 0; i < c; i++)
printf("C %d %d\n", a[i], b[i]);
return 1;
}
int main()
{
while (scanf("%d", &N) != EOF)
if (!solve())
printf("-1\n");
return 0;
}