Timus OJ 1997 Those are not the droids you're looking for (二分匹配)

题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1997

这个星球上有两种人，一种进酒吧至少玩a小时，另一种进酒吧最多玩b小时。

下面n行是人进进出出的时刻，0为进，1为出。让你求是否有合法解。

将合法的进入和出去连边，然后二分匹配就可以了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 const int N = 1e3 + 5;
 8 struct data {
 9     int a , b;
10     bool operator <(const data &cmp) const {
11         return a < cmp.a;
12     }
13 }xx[N];
14 vector <int> G[N];
15 vector <int> vc;
16 int match[N];
17 bool vis[N];
18 
19 bool dfs(int u) {
20     for(int i = 0 ; i < G[u].size() ; ++i) {
21         int v = G[u][i];
22         if(!vis[v]) {
23             vis[v] = true;
24             if(match[v] == -1 || dfs(match[v])) {
25                 match[v] = u;
26                 match[u] = v;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 
34 bool hungry() {
35     int res = 0;
36     for(int i = 0 ; i < vc.size() ; ++i) {
37         memset(vis , false , sizeof(vis));
38         if(dfs(vc[i]))
39             res++;
40     }
41     if(vc.size() == res)
42         return true;
43     return false;
44 }
45 
46 void solve() {
47     memset(match , -1 , sizeof(match));
48     if(hungry()) {
49         printf("No reason
");
50         for(int i = 0 ; i < vc.size() ; ++i) {
51             printf("%d %d
" , xx[match[vc[i]]].a , xx[vc[i]].a);
52         }
53     }
54     else {
55         printf("Liar
");
56     }
57 }
58 
59 int main()
60 {
61     int x , y , n;
62     while(~scanf("%d %d" , &x , &y)) {
63         scanf("%d" , &n);
64         int index = 0;
65         for(int i = 1 ; i <= n ; ++i) {
66             scanf("%d %d" , &xx[i].a , &xx[i].b);
67         }
68         sort(xx + 1 , xx + n + 1);
69         for(int i = 1 ; i <= n ; ++i) {
70             if(xx[i].b) {
71                 vc.push_back(i);
72                 for(int j = 1 ; j < i ; ++j) {
73                     if(!xx[j].b && (xx[i].a - xx[j].a <= y || xx[i].a - xx[j].a >= x))
74                         G[i].push_back(j);
75                 }
76             }
77         }
78         solve();
79     }
80     return 0;
81 }