1222 信与信封问题

分析：

　　先二分图匹配一下，如果不存在完美匹配（n个点全匹配成功），则直接输出none，表示有一封信不能被任何一个信封装下，根据题目可知，一定会有一个可行的方案，所以是不符的，直接输出none。（想了很长时间为什么，看了一遍题目才想过来。。。感觉输出“不合法”更好一些，或许可能存在可以确定的信呢。。）

　　然后判断每个点是不是有唯一的匹配，删除当前匹配边后，还有没有其他的匹配。判断是不是可以确定的信封。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 
 8 using namespace std;
 9 
10 const int N = 110;
11 
12 int G[N][N],match[N],T[N];
13 bool vis[N];
14 int n;
15 
16 inline int read() {
17     int x = 0,f = 1;char ch=getchar();
18     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
19     for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
20     return x*f;
21 }
22 bool dfs(int u) {
23     for (int v=1; v<=n; ++v) {
24         if (G[u][v] && !vis[v]) {
25             vis[v] = true;
26             if (!match[v] || dfs(match[v])) {
27                 match[v] = u;T[u] = v;
28                 return true;
29             }
30         }
31     }
32     return false;
33 }
34 int main() {
35     n = read();
36     for (int i=1; i<=n; ++i) 
37         for (int j=1; j<=n; ++j) G[i][j] = 1;
38     int a = read(),b = read();
39     while (a + b) {
40         G[a][b] = 0; // 左边的a与右边的b的边，不能更新G[b][a]（左边的b,右边的a） 
41         a = read(),b = read();
42     }
43     int ans = 0;
44     for (int i=1; i<=n; ++i) {
45         memset(vis,false,sizeof(vis));
46         if (dfs(i)) ans++;
47     }
48     if (ans != n) {printf("none");return 0;}
49     bool flag = false;
50     for (int u=1; u<=n; ++u) {
51         memset(vis,false,sizeof(vis));
52         int v = T[u];
53         G[u][v] = 0;
54         match[v] = 0;T[u] = 0;
55         if (!dfs(u)) {
56             printf("%d %d
",u,v);
57             match[v] = u;T[u] = v;flag = true;
58         }
59         G[u][v] = 1;
60     }
61     if (!flag) printf("none");
62     return 0;
63 }