思维题
我们仔细想想对于行列交换
如果是这种情况:
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
我们是必死的。
因为行列交换无法是我们将第一列中那聚在一块的4个1分散到其他的列中。
也就是说,行列交换无法使原本没有1的行/列有1
那么一个充分条件就是,对于每一行每一列,我们至少要有一个1.
这也是充要条件因为:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
我可以行列变化任何形状
那么直接二分图匹配吧。另外观察上面的那个矩阵。我们可以发现任何一个行交换其实都可以被列交换替代。
那么其实,我们只需要进行行交换或者列交换就够了。
对每个行哥他们匹配所对应的列。
然后记录他们的所处的行位,以及当前行位的上的行的编号。
这样说有点绕。模拟把他们移到对应的行上就可以了。
代码如下
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<vector> using namespace std; typedef pair<int, int> pii; const int inf = 2e9; const int max_n = 210; const int max_m = 41000; struct edge{ int to, next; }E[max_m << 1]; int head[max_n]; int cnt = 1; void add(int from, int to) { E[cnt].to = to;E[cnt].next = head[from]; head[from] = cnt++; } int leftTo[max_n], rightTo[max_n]; int distleft[max_n], distright[max_n]; int dist; bool seacherpath(int left_tot, int right_tot) { fill(distleft, distleft + left_tot + 1, -1); fill(distright, distright + right_tot + 1, -1); queue<int> que;dist = inf; for (int i = 1;i <= left_tot;++i) if (leftTo[i] == -1) que.push(i); while (!que.empty()) { int u = que.front();que.pop(); if (distleft[u] > dist)break; for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (distright[v] != -1)continue; distright[v] = distleft[u] + 1; if (rightTo[v] == -1)dist = distright[v]; else { distleft[rightTo[v]] = distright[v] + 1; que.push(rightTo[v]); } } }return dist != inf; } bool matchpath(int u) { for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (distright[v] != distleft[u] + 1)continue; if (distright[v] == dist && rightTo[v] != -1)continue; distright[v] = -1; if (rightTo[v] == -1 || matchpath(rightTo[v])) { leftTo[u] = v; rightTo[v] = u; return true; } }return false; } int HK(int left_tot, int right_tot) { fill(leftTo, leftTo + left_tot + 1, -1); fill(rightTo, rightTo + right_tot + 1, -1); int ans = 0; while (seacherpath(left_tot, right_tot)) { for (int i = 1;i <= left_tot;++i) if (leftTo[i] == -1 && matchpath(i)) ++ans; }return ans; } int N; int g[220][220]; int pos1[max_n]; int pos2[max_n]; int main() { while (scanf("%d", &N) != EOF) { for (int i = 1;i <= N;++i) for (int j = 1; j <= N;++j) scanf("%d", &g[i][j]); fill(head, head + max_n, 0);cnt = 1; for (int i = 1;i <= N;++i)pos1[i] = pos2[i] = i; for (int i = 1;i <= N;++i) for (int j = 1;j <= N;++j) if (g[i][j] == 1) add(i, j); int flow = HK(N, N); if (flow != N) printf("-1\n"); else { vector<pii> res; for (int i = 1;i <= N;++i) { if (pos1[i] != leftTo[i]) { res.push_back(pii(pos1[i], leftTo[i])); int exid = pos2[leftTo[i]]; swap(pos2[leftTo[i]], pos2[pos1[i]]); swap(pos1[i], pos1[exid]); } }printf("%d\n", res.size()); for (pii p : res)printf("R %d %d\n", p.first, p.second); } } }