HDU 2819 Swap【二分图|启发题】

大意：

0 1

1 0
告诉你如上图的矩阵然后你每次可以交换两行或者两列问能否经过若干次交换让主对角线上的数字都变成一然后输出交换的操作

分析：

这个题可以用二分图匹配来做

比如这个矩阵

1 0 0

0 0 1

0 1 0

我们先对x,y建立二分图之后得到

1 -- 1

2 -- 3

3 -- 2

只要两个数一样说明这个1在对角线上也就是不用移动

如果2 -- 3

也就是说2 行 3列有个1

我们想把它换到2行2列上

那就直接交换就可以了

也就是说直接交换第二列和第三列

然后按照二分图的匹配方式依次的进行交换

要注意的是我们每次交换的是该行的实际位置

所以用一个数组来记录就可以了

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef pair<int, int> PII;
 8 const int maxn = 105;
 9 int a[maxn][maxn];
10 int num[maxn];
11 int n;
12 
13 struct Edge {
14     int to, next;
15 }e[maxn * maxn];
16 int head[maxn];
17 int tot;
18 
19 void add(int u, int v) {
20     e[tot].to = v;
21     e[tot].next = head[u];
22     head[u] = tot++;
23 }
24 
25 int Link[maxn];int vis[maxn];
26 bool Find(int u) {
27     for(int i = head[u]; i; i = e[i].next) {
28         int v = e[i].to;
29         if(!vis[v]) {
30             vis[v] = 1;
31             if(Link[v] == -1 || Find(Link[v]) ) {
32                 Link[v] = u;
33                 return true;
34             }
35         }
36     }
37     return false;
38 }
39 int solve() {
40     memset(Link, -1, sizeof(Link));
41     int cnt = 0;
42     for(int i = 1; i <= n; i++) {
43         memset(vis, 0, sizeof(vis));
44         if(Find(i)) cnt++;
45     }
46     return cnt;
47 }
48 
49 void init() {
50     tot = 1;
51     memset(head, 0, sizeof(head));
52     for(int i = 1; i <= n; i++) {
53         num[i] = i;
54     }
55 }
56 PII p[maxn];
57 
58 int main() {
59     while(EOF != scanf("%d",&n) ) {
60         init();
61         for(int i = 1; i <= n; i++) {
62             for(int j = 1; j <= n; j++) {
63                 scanf("%d",&a[i][j]);
64                 if(a[i][j] == 1) {
65                     add(i, j);
66                 }
67             }
68         }
69         int ans = solve();
70         if(ans != n) {
71             puts("-1");
72             continue;
73         }
74         int cnt = 0;
75         for(int i = 1; i <= n; i++) {
76             int x = Link[i]; int y = i;
77             int xx, yy;
78             if(x == y) continue;
79             for(int i = 1; i <= n; i++) {
80                 if(num[i] == y) {
81                     yy = i;
82                     break;
83                 }
84             }
85             if(x == yy) continue;
86             p[cnt++] = make_pair(x, yy);
87             swap(num[x], num[yy]);
88         }
89         printf("%d
", cnt);
90         for(int i = 0; i < cnt; i++) {
91             printf("C %d %d
", p[i].first, p[i].second);
92         }
93     }
94     return 0;
95 }

View Code