這題的目的是，通過一系列交換，讓矩陣中A[i, i] (1 <= i <= N)的值全為1。
首先要明確：
如果某行或者某列全是0。那怎么換都沒辦法的。
否則，一定能換出來。
這個動動腦子想一下可以明白的。
其次要明確：只交換行或者只交換列都是可以換出來的。
這個動動腦子想一下也可以明白的。
明確了這兩點(diǎn)，這問題就變成了二分圖的匹配問題。
二分圖左邊的節(jié)點(diǎn)為每一行的行號
二分圖右邊的節(jié)點(diǎn)為每一行中出現(xiàn)的“1”對應(yīng)的列號
這樣用匈牙利算法就可以匹配了。
#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;
}