Swap HDU - 2819

思维题

我们仔细想想对于行列交换
如果是这种情况：
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);
        }
    }
}