FZU 1202 信与信封问题 二分图匹配

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <functional>
14 #include <time.h>
15 
16 using namespace std;
17 
18 const int INF = 1<<30;
19 const int MAXN = 105;
20 
21 
22 bool Matrix[MAXN][MAXN];
23 int n;
24 
25 int mX[MAXN], mY[MAXN], visX[MAXN], visY[MAXN];
26 
27 bool dfs(int u) {
28     visX[u] = true;
29     for (int v = 1; v <= n; v++) if (!Matrix[u][v] && !visY[v]) {
30         visY[v] = true;
31         if (mY[v]<0 || dfs(mY[v])) {
32             mY[v] = u;
33             mX[u] = v;
34             return true;
35         }
36     }
37     return false;
38 }
39 
40 void input() {
41     memset(Matrix, false, sizeof(Matrix));
42     int x, y;
43     while (scanf("%d%d", &x, &y)!=EOF && (x!=0||y!=0)) {
44         Matrix[x][y] = true;
45     }
46 }
47 
48 void solve() {
49     int Max;
50     memset(mX, -1, sizeof(mX));
51     memset(mY, -1, sizeof(mY));
52     for (int i = 1; i <= n; i++) {
53         memset(visX, false, sizeof(visX));
54         memset(visY, false, sizeof(visY));
55         if (dfs(i)) Max++;
56     }
57     if (Max<n) {
58         puts("none");
59         return ;
60     }
61     bool flag = true;
62     int delX, delY;
63     for (int i = 1; i <= n; i++) {
64         delX = i; delY = mX[i];
65         mX[delX] = mY[delY] = -1;
66         Matrix[delX][delY] = true;
67         memset(visX, false, sizeof(visX));
68         memset(visY, false, sizeof(visY));
69 
70         if (!dfs(i)) {
71             printf("%d %d\n", delX, delY);
72             mX[delX] = delY; mY[delY] = delX;
73             flag = false;
74         }
75         Matrix[delX][delY] = false;
76     }
77     if (flag) puts("none");
78 }
79 
80 int main() {
81     #ifdef Phantom01
82         freopen("FZU1202.txt", "r", stdin);
83     #endif //Phanaom01
84 
85     while (scanf("%d", &n)!=EOF) {
86         input();
87         solve();
88         puts("");
89     }
90 
91     return 0;
92 }