[kuangbin]带你飞之'匹配问题'专题

专题十匹配问题
√ HDU 1045 Fire Net
√ HDU 2444 The Accomodation of Students
√ HDU 1083 Courses
√ HDU 1281 棋盘游戏
√ HDU 2819 Swap
√ HDU 2389 Rain on your Parade
√ HDU 4185 Oil Skimming
√ POJ 3020 Antenna Placement
√ HDU 1054 Strategic Game
√ HDU 1151 Air Raid
√ POJ 2594 Treasure Exploration
√ HDU 3829 Cat VS Dog
√ POJ 2289 Jamie's Contact Groups
√ POJ 2112 Optimal Milking
√ POJ 3189 Steady Cow Assignment
√ HDU 2255 奔小康赚大钱
√ HDU 3488 Tour
√ URAL 1099 Work Scheduling
HDU 4687 Boke and Tsukkomi

// hdu 1045

 1 #include<cstdio>
 2 
 3 int n, maxn;
 4 char G[4][4];
 5 
 6 bool read_input() {
 7     if(scanf("%d", &n) == 1 && !n) return false;
 8     for(int i = 0; i != n; ++i) {
 9         scanf("%s", G[i]);
10     }
11     return true;
12 }
13 
14 bool can_put(int r, int c) {
15     if(G[r][c] == 'X') return false;
16     int i, j;
17     j = c;
18     while(j >= 0 && G[r][j] != 'X') {
19         if(j != c && G[r][j] == '1') return false;
20         --j;
21     }
22     j = c;
23     while(j != n && G[r][j] != 'X') {
24         if(j != c && G[r][j] == '1') return false;
25         ++j;
26     }
27     i = r;
28     while(i >= 0 && G[i][c] != 'X') {
29         if(i != r && G[i][c] == '1') return false;
30         --i;
31     }
32     i = r;
33     while(i != n && G[i][c] != 'X') {
34         if(i != r && G[i][c] == '1') return false;
35         ++i;
36     }
37     return true;
38 }
39 
40 void dfs(int r, int c, int v) {
41     if(r == n) {
42         if(v > maxn) maxn = v;
43         return;
44     }
45     if(can_put(r, c)) {
46         G[r][c] = '1';
47         if(c == n-1) dfs(r+1, 0, v+1);
48         else dfs(r, c+1, v+1);
49         G[r][c] = '.';
50     }
51     if(c == n-1) dfs(r+1, 0, v);
52     else dfs(r, c+1, v);
53 }
54 
55 
56 int main() {
57     while(read_input()) {
58         maxn = 0;
59         dfs(0, 0, 0);
60         printf("%d
", maxn);
61     }
62     return 0;
63 }

View Code

// hdu 2444

 1 #include<cstdio>
 2 #include<queue>
 3 using namespace std;
 4 const int MAXN = 200+5;
 5 const int MAXM = MAXN*MAXN;
 6 
 7 int num;
 8 int head[MAXN];
 9 struct node {
10     int v, next;
11 } edge[MAXM];
12 
13 inline void add(int x, int y) {
14     edge[num].v = y;
15     edge[num].next = head[x];
16     head[x] = num++;
17 }
18 
19 int n, m;
20 int color[MAXN];
21 
22 bool bfs(int s) {
23     queue<int> q;
24     q.push(s);
25     color[s] = 0;
26     while(!q.empty()) {
27         int u = q.front();
28         q.pop();
29         for(int i = head[u]; i != -1; i = edge[i].next) {
30             int v = edge[i].v;
31             if(color[v] == -1) q.push(v), color[v] = !color[u];
32             if(color[u] == color[v]) return false;
33         }
34     }
35     return true;
36 }
37 
38 bool is_binG() {
39     for(int i = 1; i <= n; ++i) color[i] = -1;
40     for(int i = 1; i <= n; ++i) if(color[i] == -1 && !bfs(i)) return false;
41     return true;
42 }
43 
44 int love[MAXN];
45 bool vis[MAXN];
46 bool dfs(int u) {
47     for(int i = head[u]; i != -1; i = edge[i].next) {
48         int v = edge[i].v;
49         if(!vis[v]) {
50             vis[v] = true;
51             if(!love[v] || dfs(love[v])) {
52                 love[v] = u;
53                 return true;
54             }
55         }
56     }
57     return false;
58 }
59 
60 int hungry() {
61     int ans = 0;
62     for(int i = 1; i <= n; ++i) love[i] = 0;
63     for(int i = 1; i <= n; ++i) {
64         for(int j = 1; j <= n; ++j) vis[j] = false;
65         if(dfs(i)) ++ans;
66     }
67     return ans;
68 }
69 
70 int main() {
71     while(scanf("%d%d", &n, &m) == 2) {
72         num = 0;
73         for(int i = 1; i <= n; ++i) head[i] = -1;
74         int x, y;
75         for(int i = 0; i != m; ++i) {
76             scanf("%d%d", &x, &y);
77             add(x, y); add(y, x);
78         }
79         if(!is_binG()) printf("No
");
80         else printf("%d
", hungry()/2);
81     }
82     return 0;
83 }

View Code

// hdu 1083

 1 #include<cstdio>
 2 using namespace std;
 3 const int MAXN = 1000+5;
 4 const int MAXM = 3000+5;
 5 
 6 int num;
 7 int head[MAXN];
 8 struct node {
 9     int v, next;
10 } edge[MAXN*MAXM];
11 
12 inline void add(int x, int y) {
13     edge[num].v = y;
14     edge[num].next = head[x];
15     head[x] = num++;
16 }
17 
18 int n, m;
19 int nm[MAXN];
20 
21 int love[MAXM];
22 bool vis[MAXM];
23 bool dfs(int u) {
24     for(int i = head[u]; i != -1; i = edge[i].next) {
25         int v = edge[i].v;
26         if(!vis[v]) {
27             vis[v] = true;
28             if(!love[v] || dfs(love[v])) {
29                 love[v] = u;
30                 return true;
31             }
32         }
33     }
34     return false;
35 }
36 
37 bool solve() {
38     for(int i = 1; i <= m; ++i) love[i] = 0;
39     for(int i = 1; i <= n; ++i) {
40         for(int j = 1; j <= m; ++j) vis[j] = false;
41         if(nm[i] && !dfs(i)) return false;
42     }
43     return true;
44 }
45 
46 int main() {
47     int T;
48     scanf("%d", &T);
49     while(T--) {
50         scanf("%d%d", &n, &m);
51         for(int i = 1; i <= n; ++i) head[i] = -1;
52         int p;
53         for(int i = 1; i <= n; ++i) {
54             scanf("%d", &nm[i]);
55             for(int j = 0; j != nm[i]; ++j) {
56                 scanf("%d", &p);
57                 add(i, p);
58             }
59         }
60         if(solve()) printf("YES
");
61         else printf("NO
");
62     }
63     return 0;
64 }

View Code

// hdu 1281

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 100 + 10;
 6 
 7 int n, m, k, ans, a2, cnt;
 8 int pic[maxn][maxn];
 9 int used[maxn];
10 int match[maxn];
11 
12 bool read_input() {
13     if(scanf("%d", &n) != 1 )return false;
14     memset(pic, 0, sizeof(pic));
15     memset(match, 0, sizeof(match));
16     scanf("%d%d", &m, &k);
17     int x, y;
18     for(int i = 0; i != k; ++i) {
19         scanf("%d%d", &x, &y);
20         pic[x][y] = 1;
21     }
22     return true;
23 }
24 
25 bool can_find(int x) {
26     for(int i = 1; i <= m; ++i) {
27         if(pic[x][i] && !used[i]) {
28             used[i] = 1;
29             if(!match[i] || can_find(match[i])) {
30                 match[i] = x;
31                 return true;
32             }
33         }
34     }
35     return false;
36 }
37 
38 int m2[maxn];
39 
40 bool find2(int x) {
41     for(int i = 1; i <= m; ++i) {
42         if(pic[x][i] && !used[i]) {
43             used[i] = 1;
44             if(!m2[i] || can_find(m2[i])) {
45                 m2[i] = x;
46                 return true;
47             }
48         }
49     }
50     return false;
51 }
52 
53 void fn(int x, int y) {
54     pic[x][y] = 0;
55     a2 = 0;
56     memset(m2, 0, sizeof(m2));
57     for(int i = 1; i <= n; ++i) {
58         memset(used, 0, sizeof(used));
59         if(find2(i)) ++a2;
60     }
61     if(a2 != ans) ++cnt;
62     pic[x][y] = 1;
63 }
64 
65 int main() {
66     int kase = 0;
67     while(read_input()) {
68         ans = 0;
69         cnt = 0;
70         for(int i = 1; i <= n; ++i) {
71             memset(used, 0, sizeof(used));
72             if(can_find(i)) ++ans;
73         }
74         for(int i = 1; i <= m; ++i) {
75             if(match[i]) {
76                 fn(match[i], i);
77             }
78         }
79         printf("Board %d have %d important blanks for %d chessmen.
", ++kase, cnt, ans);
80     }
81     return 0;
82 }

View Code

// hdu 2819

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 const int MAXN = 100+5;
 5 typedef pair<int,int> Pair;
 6 
 7 int num;
 8 int head[MAXN];
 9 struct node {
10     int v, next;
11 } edge[MAXN*MAXN];
12 
13 inline void add(int x, int y) {
14     edge[num].v = y;
15     edge[num].next = head[x];
16     head[x] = num++;
17 }
18 
19 int n;
20 
21 int love[MAXN];
22 bool vis[MAXN];
23 int need[MAXN], idx[MAXN];
24 
25 bool dfs(int u) {
26     for(int i = head[u]; i != -1; i = edge[i].next) {
27         int v = edge[i].v;
28         if(!vis[v]) {
29             vis[v] = true;
30             if(!love[v] || dfs(love[v])) {
31                 love[v] = u;
32                 need[u] = v;
33                 return true;
34             }
35         }
36     }
37     return false;
38 }
39 
40 void solve() {
41     for(int i = 1; i <= n; ++i) love[i] = 0, idx[i] = i;
42     for(int i = 1; i <= n; ++i) {
43         for(int j = 1; j <= n; ++j) vis[j] = false;
44         if(!dfs(i)) {
45             printf("-1
");
46             return ;
47         }
48     }
49     int ans = 0;
50     vector<Pair> v;
51     for(int i = 1; i <= n; ++i) {
52         if(need[i] == i) continue;
53         ++ans;
54         int p = need[i];
55         v.push_back(make_pair(i, p));
56         need[love[i]] = p;
57         love[p] = love[i];
58     }
59     printf("%d
", ans);
60     for(int i = 0; i != v.size(); ++i) printf("C %d %d
", v[i].first, v[i].second);
61 }
62 
63 int main() {
64     while(scanf("%d", &n) == 1) {
65         num = 0;
66         for(int i = 1; i <= n; ++i) head[i] = -1;
67         int x;
68         for(int i = 1; i <= n; ++i) {
69             for(int j = 1; j <= n; ++j) {
70                 scanf("%d", &x);
71                 if(x) add(i, j);
72             }
73         }
74         solve();
75     }
76     return 0;
77 }

View Code

// hdu 2389

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<queue>
  5 #define eps 1e-8
  6 #define INF 0x3f3f3f3f
  7 using namespace std;
  8 const int MAXN = 3000+5;
  9 const int MAXM = MAXN*MAXN;
 10 
 11 int num;
 12 int head[MAXN];
 13 struct node {
 14     int v, next;
 15 } edge[MAXM];
 16 
 17 inline void add(int x, int y) {
 18     edge[num].v = y;
 19     edge[num].next = head[x];
 20     head[x] = num++;
 21 }
 22 
 23 double t;
 24 int n, m;
 25 double px[MAXN], py[MAXN], pv[MAXN];
 26 
 27 int dis;
 28 int cx[MAXN], cy[MAXN];
 29 int dx[MAXN], dy[MAXN];
 30 bool vis[MAXN];
 31 
 32 bool bfs_findPath() {
 33     for(int i = 1; i <= n; ++i) dx[i] = -1;
 34     for(int i = 1; i <= m; ++i) dy[i] = -1;
 35     queue<int> q;
 36     dis = INF;
 37     for(int i = 1; i <= n; ++i) if(cx[i] == -1) q.push(i), dx[i] = 0;
 38     while(!q.empty()) {
 39         int u = q.front();
 40         q.pop();
 41         if(dx[u] > dis) break;
 42         for(int i = head[u]; i != -1; i = edge[i].next) {
 43             int v = edge[i].v;
 44             if(dy[v] == -1) {
 45                 dy[v] = dx[u] + 1;
 46                 if(cy[v] == -1) dis = dy[v];
 47                 else {
 48                     dx[cy[v]] = dy[v] + 1;
 49                     q.push(cy[v]);
 50                 }
 51             }
 52         }
 53     }
 54     return dis != INF;
 55 }
 56 
 57 bool dfs(int u) {
 58     for(int i = head[u]; i != -1; i = edge[i].next) {
 59         int v = edge[i].v;
 60         if(!vis[v] && dy[v] == dx[u] + 1) {
 61             vis[v] = 1;
 62             if(cy[v] != -1 && dy[v] == dis) continue;
 63             if(cy[v] == -1 || dfs(cy[v])) {
 64                 cx[u] = v;
 65                 cy[v] = u;
 66                 return true;
 67             }
 68         }
 69     }
 70     return false;
 71 }
 72 
 73 int HK() {
 74     int ans = 0;
 75     for(int i = 1; i <= n; ++i) cx[i] = -1;
 76     for(int i = 1; i <= m; ++i) cy[i] = -1;
 77     while(bfs_findPath()) {
 78         for(int i = 1; i <= n; ++i) {
 79             for(int j = 1; j <= m; ++j) vis[j] = false;
 80             if(cx[i] == -1 && dfs(i)) ++ans;
 81         }
 82     }
 83     return ans;
 84 }
 85 
 86 int main() {
 87     int T, cnt = 0;
 88     scanf("%d", &T);
 89     while(T--) {
 90         scanf("%lf", &t);
 91         scanf("%d", &m);
 92         for(int i = 1; i <= m; ++i) scanf("%lf%lf%lf", &px[i], &py[i], &pv[i]);
 93         scanf("%d", &n);
 94         num = 0;
 95         for(int i = 1; i <= n; ++i) head[i] = -1;
 96         for(int i = 1; i <= n; ++i) {
 97             double x, y;
 98             scanf("%lf%lf", &x, &y);
 99             for(int j = 1; j <= m; ++j) {
100                 if(sqrt((x-px[j])*(x-px[j])+(y-py[j])*(y-py[j]))/pv[j] <= t) add(i, j);
101             }
102         }
103         printf("Scenario #%d:
%d

", ++cnt, HK());
104     }
105     return 0;
106 }

View Code

// hdu 4185

 1 #include<cstdio>
 2 #include<map>
 3 #define rep(i, n) for(int i=0;i!=n;++i)
 4 #define rep1(i, n) for(int i=1;i<=n;++i)
 5 using namespace std;
 6 const int MAXN = 605*605+5;
 7 typedef pair<int,int> Pair;
 8 
 9 const int fx[] = {-1, 1, 0, 0};
10 const int fy[] = { 0, 0,-1, 1};
11 
12 int num;
13 int head[MAXN];
14 struct node {
15     int v, next;
16 } edge[MAXN*2];
17 
18 inline void add(int x, int y) {
19     edge[num].v = y;
20     edge[num].next = head[x];
21     head[x] = num++;
22 }
23 
24 int n, m;
25 char G[605][605];
26 
27 int love[MAXN];
28 bool vis[MAXN];
29 
30 bool dfs(int u) {
31     for(int i = head[u]; i != -1; i = edge[i].next) {
32         int v = edge[i].v;
33         if(!vis[v]) {
34             vis[v] = true;
35             if(!love[v] || dfs(love[v])) {
36                 love[v] = u;
37                 return true;
38             }
39         }
40     }
41     return false;
42 }
43 
44 int hungry() {
45     int ans = 0;
46     for(int i = 1; i <= n; ++i) love[i] = 0;
47     for(int i = 1; i <= n; ++i) {
48         for(int j = 1; j <= n; ++j) vis[j] = false;
49         if(dfs(i)) ++ans;
50     }
51     return ans;
52 }
53 
54 int main() {
55     int T, cnt = 0;
56     scanf("%d", &T);
57     while(T--) {
58         scanf("%d", &m);
59         num = 0;
60         rep1(i, m*m) head[i] = -1;
61         map<Pair,int> id;
62         
63         n = 0;
64         rep(i, m) {
65             scanf("%s", G[i]);
66             rep(j, m) if(G[i][j] == '#') {
67                 Pair p = make_pair(i, j);
68                 id[p] = ++n;
69             }
70         }
71         rep(i, m) rep(j, m) if(G[i][j] == '#') {
72             for(int k = 0; k != 4; ++k) {
73                 int nx = i+fx[k];
74                 int ny = j+fy[k];
75                 if(nx<0||nx==m||ny<0||ny==m) continue;
76                 if(G[nx][ny] == '#') add(id[make_pair(i,j)], id[make_pair(nx,ny)]);
77             }
78         }
79         printf("Case %d: %d
", ++cnt, hungry()/2);
80     }
81     return 0;
82 }

View Code

// poj 3020

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<fstream>
  5 #include<iostream>
  6 #include<string>
  7 #include<functional>
  8 #include<algorithm>
  9 #include<sstream>
 10 #include<iomanip>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<set>
 15 #include<map>
 16 #define read(n) n = read_n()
 17 #define rep(i, n) for(int i=0;i!=n;++i)
 18 #define per(i, n) for(int i=n-1;i>=0;--i)
 19 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 20 #define rep1(i, n) for(int i=1;i<=n;++i)
 21 #define per1(i, n) for(int i=n;i>=1;--i)
 22 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 23 #define L k<<1
 24 #define R k<<1|1
 25 #define mid (tree[k].l+tree[k].r)>>1
 26 #define eps 1e-10
 27 using namespace std;
 28 const int INF = 0x3f3f3f3f;
 29 typedef long long ll;
 30 
 31 inline int read_n() {
 32     char c=getchar();int x=0,f=1;
 33     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 34     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 35     return x*f;
 36 }
 37 // -----------------------------------------------------
 38 const int MAXN = 40*10+5;
 39 const int MAXM = MAXN*4;
 40 typedef pair<int,int> Pair;
 41 
 42 const int fx[] = {-1, 1, 0, 0};
 43 const int fy[] = { 0, 0,-1, 1};
 44 
 45 int num;
 46 int head[MAXN];
 47 struct node {
 48     int v, next;
 49 } edge[MAXM];
 50 
 51 inline void add(int x, int y) {
 52     edge[num].v = y;
 53     edge[num].next = head[x];
 54     head[x] = num++;
 55 }
 56 
 57 int h, w;
 58 string G[45];
 59 
 60 int n;
 61 int love[MAXN];
 62 bool vis[MAXN];
 63 
 64 bool dfs(int u) {
 65     for(int i = head[u]; i != -1; i = edge[i].next) {
 66         int v = edge[i].v;
 67         if(!vis[v]) {
 68             vis[v] = true;
 69             if(!love[v] || dfs(love[v])) {
 70                 love[v] = u;
 71                 return true;
 72             }
 73         }
 74     }
 75     return false;
 76 }
 77 
 78 void solve() {
 79     int ans = 0;
 80     rep1(i, n) love[i] = 0;
 81     rep1(i, n) {
 82         rep1(j, n) vis[j] = false;
 83         if(dfs(i)) ++ans;
 84     }
 85     ans /= 2;
 86     printf("%d
", ans+n-ans*2);
 87 }
 88 
 89 int main() {
 90     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 91     int T;
 92     cin >> T;
 93     while(T--) {
 94         cin >> h >> w;
 95         n = 0;
 96         map<Pair,int> id;
 97         rep(i, h) {
 98             cin >> G[i];
 99             rep(j, w) if(G[i][j] == '*') id[make_pair(i,j)] = ++n;
100         }
101         
102         num = 0;
103         rep1(i, n) head[i] = -1;
104         rep(i, h) rep(j, w) if(G[i][j] == '*') {
105             for(int k = 0; k != 4; ++k) {
106                 int nx = i+fx[k];
107                 int ny = j+fy[k];
108                 if(nx<0||nx==h||ny<0||ny==w) continue;
109                 if(G[nx][ny] == '*') add(id[make_pair(i,j)], id[make_pair(nx,ny)]);
110             }
111         }
112         solve();
113     }
114     return 0;
115 }

View Code

// hdu 1054

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 
 6 int n;
 7 vector<int> edges[1505];
 8 int vis[1505];
 9 int match[1505];
10 
11 bool marry(int x) {
12     for(int i = 0; i != edges[x].size(); ++i) {
13         int v = edges[x][i];
14         if(!vis[v]) {
15             vis[v] = 1;
16             if(match[v] == -1 || marry(match[v])) {
17                 match[v] = x;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 
25 int main() {
26     while(scanf("%d", &n) == 1) {
27         int f, num, x;
28         for(int i = 0; i != n; ++i) edges[i].clear();
29         for(int i = 0; i != n; ++i) {
30             scanf("%d:(%d)", &f, &num);
31             for(int j = 0; j != num; ++j) {
32                 scanf("%d", &x);
33                 edges[f].push_back(x);
34                 edges[x].push_back(f);
35             }
36         }
37         int sum = 0;
38         memset(match, -1, sizeof(match));
39         for(int i = 0; i != n; ++i) {
40             memset(vis, 0, sizeof(vis));
41             if(marry(i)) sum++;
42         }
43         printf("%d
", sum/2);
44     }
45     return 0;
46 }

View Code

// hdu 1151

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<fstream>
  5 #include<iostream>
  6 #include<string>
  7 #include<functional>
  8 #include<algorithm>
  9 #include<sstream>
 10 #include<iomanip>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<set>
 15 #include<map>
 16 #define read(n) n = read_n()
 17 #define rep(i, n) for(int i=0;i!=n;++i)
 18 #define per(i, n) for(int i=n-1;i>=0;--i)
 19 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 20 #define rep1(i, n) for(int i=1;i<=n;++i)
 21 #define per1(i, n) for(int i=n;i>=1;--i)
 22 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 23 #define L k<<1
 24 #define R k<<1|1
 25 #define mid (tree[k].l+tree[k].r)>>1
 26 #define eps 1e-10
 27 using namespace std;
 28 const int INF = 0x3f3f3f3f;
 29 typedef long long ll;
 30 
 31 inline int read_n() {
 32     char c=getchar();int x=0,f=1;
 33     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 34     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 35     return x*f;
 36 }
 37 // -----------------------------------------------------
 38 const int MAXN = 120+5;
 39 
 40 int num;
 41 int head[MAXN];
 42 struct node {
 43     int v, next;
 44 } edge[MAXN];
 45 
 46 inline void add(int x, int y) {
 47     edge[num].v = y;
 48     edge[num].next = head[x];
 49     head[x] = num++;
 50 }
 51 
 52 int n, m;
 53 
 54 int love[MAXN];
 55 bool vis[MAXN];
 56 
 57 bool dfs(int u) {
 58     for(int i = head[u]; i != -1; i = edge[i].next) {
 59         int v = edge[i].v;
 60         if(!vis[v]) {
 61             vis[v] = true;
 62             if(!love[v] || dfs(love[v])) {
 63                 love[v] = u;
 64                 return true;
 65             }
 66         }
 67     }
 68     return false;
 69 }
 70 
 71 int hungry() {
 72     int ans = 0;
 73     rep1(i, n) love[i] = 0;
 74     rep1(i, n) {
 75         rep1(j, n) vis[j] = false;
 76         if(dfs(i)) ++ans;
 77     }
 78     return ans;
 79 }
 80 
 81 int main() {
 82     //ofstream outputfile;
 83     //outputfile.open();Output.txt
 84     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 85     int T;
 86     cin >> T;
 87     while(T--) {
 88         cin >> n;
 89         num = 0;
 90         rep1(i, n) head[i] = -1;
 91         cin >> m;
 92         int x, y;
 93         rep(i, m) {
 94             cin >> x >> y;
 95             add(x, y);
 96         }
 97         cout << n-hungry() << endl;
 98     }
 99     
100     //outputfile.close();
101     return 0;
102 }

View Code

// poj 2594

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-11-04 11:23:42
  7  * @LastEditTime: 2019-11-04 12:42:41
  8  */
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<cmath>
 12 #include<fstream>
 13 #include<iostream>
 14 #include<string>
 15 #include<functional>
 16 #include<algorithm>
 17 #include<sstream>
 18 #include<iomanip>
 19 #include<vector>
 20 #include<queue>
 21 #include<stack>
 22 #include<set>
 23 #include<map>
 24 #define read(n) n = read_n()
 25 #define rep(i, n) for(int i=0;i!=n;++i)
 26 #define per(i, n) for(int i=n-1;i>=0;--i)
 27 #define Rep(i, sta, n) for(int i=sta;i!=n;++i)
 28 #define rep1(i, n) for(int i=1;i<=n;++i)
 29 #define per1(i, n) for(int i=n;i>=1;--i)
 30 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
 31 #define L k<<1
 32 #define R k<<1|1
 33 #define mid (tree[k].l+tree[k].r)>>1
 34 #define eps 1e-10
 35 using namespace std;
 36 const int INF = 0x3f3f3f3f;
 37 typedef long long ll;
 38 
 39 inline int read_n() {
 40     char c=getchar();int x=0,f=1;
 41     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 42     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 43     return x*f;
 44 }
 45 // -----------------------------------------------------
 46 const int MAXN = 500+5;
 47 
 48 int num;
 49 int head[MAXN];
 50 struct node {
 51     int v, next;
 52 } edge[MAXN*MAXN];
 53 
 54 inline void add(int x, int y) {
 55     edge[num].v = y;
 56     edge[num].next = head[x];
 57     head[x] = num++;
 58 }
 59 
 60 int n, m;
 61 int G[MAXN][MAXN];
 62 
 63 int love[MAXN];
 64 bool vis[MAXN];
 65 
 66 bool dfs(int u) {
 67     for(int i = head[u]; i != -1; i = edge[i].next) {
 68         int v = edge[i].v;
 69         if(!vis[v]) {
 70             vis[v] = true;
 71             if(!love[v] || dfs(love[v])) {
 72                 love[v] = u;
 73                 return true;
 74             }
 75         }
 76     }
 77     return false;
 78 }
 79 
 80 int hungry() {
 81     int ans = 0;
 82     rep1(i, n) love[i] = false;
 83     rep1(i, n) {
 84         rep1(j, n) vis[j] = false;
 85         if(dfs(i)) ++ans;
 86     }
 87     return ans;
 88 }
 89 
 90 int main() {
 91     //ofstream outputfile;
 92     //outputfile.open();Output.txt
 93     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 94     while(cin >> n >> m && n) {
 95         num = 0;
 96         rep1(i, n) head[i] = -1;
 97         rep1(i, n) rep1(j, n) G[i][j] = 0;
 98         int x, y;
 99         rep(i, m) {
100             cin >> x >> y;
101             G[x][y] = 1;
102         }
103         rep1(k, n) rep1(i, n) if(G[i][k]) {
104             rep1(j, n) if(G[k][j]) G[i][j] = 1;
105         }
106         rep1(i, n) rep1(j, n) if(G[i][j]) add(i, j);
107         cout << n-hungry() << endl;
108     }
109     
110     //outputfile.close();
111     return 0;
112 }

View Code

// hdu 3829

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-11-04 13:03:15
 7  * @LastEditTime: 2019-11-04 13:34:29
 8  */
 9 #include<iostream>
10 #include<string>
11 #define rep(i, n) for(int i=0;i!=n;++i)
12 #define rep1(i, n) for(int i=1;i<=n;++i)
13 using namespace std;
14 // -----------------------------------------------------
15 const int MAXN = 500+5;
16 const int MAXE = MAXN*MAXN;
17 
18 int num;
19 int head[MAXN];
20 struct node {
21     int v, next;
22 } edge[MAXE];
23 
24 inline void add(int x, int y) {
25     edge[num].v = y;
26     edge[num].next = head[x];
27     head[x] = num++;
28 }
29 
30 int cat, dog, n;
31 
32 int love[MAXN];
33 bool vis[MAXN];
34 
35 bool dfs(int u) {
36     for(int i = head[u]; i != -1; i = edge[i].next) {
37         int v = edge[i].v;
38         if(!vis[v]) {
39             vis[v] = 1;
40             if(!love[v] || dfs(love[v])) {
41                 love[v] = u;
42                 return true;
43             }
44         }
45     }
46     return false;
47 }
48 
49 int hungry() {
50     int ans = 0;
51     rep1(i, n) love[i] = 0;
52     rep1(i, n) {
53         rep1(j, n) vis[j] = false;
54         if(dfs(i)) ++ans;
55     }
56     return ans;
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
61     while(cin >> cat >> dog >> n) {
62         num = 0;
63         rep1(i, n) head[i] = -1;
64         string l[MAXN], r[MAXN];
65         rep1(i, n) {
66             cin >> l[i] >> r[i];
67             rep1(j, i-1) if(r[i] == l[j] || l[i] == r[j]) add(j, i), add(i, j);
68         }
69         cout << n-hungry()/2 << "
";
70     }
71     return 0;
72 }

View Code

// poj 2289

 1 #include<iostream>
 2 #include<sstream>
 3 #include<cstdlib>
 4 using namespace std;
 5 
 6 const int MAXN = 1000+5;
 7 const int MAXM = 500+5;
 8 const int MAXE = MAXN*MAXM;
 9 
10 int num;
11 int head[MAXN];
12 struct node {
13     int v, next;
14 } edge[MAXE];
15 
16 inline void add(int x, int y) {
17     edge[num].v = y;
18     edge[num].next = head[x];
19     head[x] = num++;
20 }
21 
22 int n, m, maxn;
23 string str;
24 
25 int cnt[MAXN];
26 int love[MAXN][MAXM];
27 bool vis[MAXN];
28 
29 bool dfs(int u) {
30     for(int i = head[u]; i != -1; i = edge[i].next) {
31         int v = edge[i].v;
32         if(!vis[v]) {
33             vis[v] = true;
34             if(cnt[v] < maxn) {
35                 love[v][++cnt[v]] = u;
36                 return true;
37             }
38             for(int j = 1; j <= cnt[v]; ++j) {
39                 if(dfs(love[v][j])) {
40                     love[v][j] = u;
41                     return true;
42                 }
43             }
44         }
45     }
46     return false;
47 }
48 
49 bool hungry(int p) {
50     maxn = p;
51     for(int i = 0; i != m; ++i) cnt[i] = 0;
52     for(int i = 1; i <= n; ++i) {
53         for(int j = 0; j != m; ++j) vis[j] = false;
54         if(!dfs(i)) return false;
55     }
56     return true;
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
61     while(cin >> n >> m && n) {
62         num = 0;
63         getchar();
64         for(int i = 1; i <= n; ++i) head[i] = -1;
65         for(int i = 1; i <= n; ++i) {
66             getline(cin, str);
67             stringstream s(str);
68             string ss;
69             while(s >> ss) {
70                 if(isalpha(ss[0])) continue;
71                 int p = atoi(ss.c_str());
72                 add(i, p);
73             }
74         }
75         int l = 1, r = n, mid, ans;
76         while(l <= r) {
77             mid = (l+r)/2;
78             if(hungry(mid)) ans = mid, r = mid - 1;
79             else l = mid + 1;
80         }
81         cout << ans << "
";
82     }
83     return 0;
84 }

View Code

// poj 2112

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-11-04 17:14:42
 7  * @LastEditTime: 2019-11-04 22:29:54
 8  */
 9 #include<iostream>
10 #include<algorithm>
11 #include<vector>
12 #define rep(i, n) for(int i=0;i!=n;++i)
13 #define rep1(i, n) for(int i=1;i<=n;++i)
14 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
15 using namespace std;
16 // -----------------------------------------------------
17 const int MAXN = 230+5;
18 const int MAXE = MAXN*MAXN;
19 
20 int num;
21 int head[MAXN];
22 struct node {
23     int v, next;
24 } edge[MAXE];
25 
26 inline void add(int x, int y) {
27     edge[num].v = y;
28     edge[num].next = head[x];
29     head[x] = num++;
30 }
31 
32 int n, m, nm, maxn, dis;
33 int G[MAXN][MAXN];
34 
35 int cnt[MAXN];
36 int love[MAXN][MAXN];
37 bool vis[MAXN];
38 
39 bool dfs(int u) {
40     for(int i = head[u]; i != -1; i = edge[i].next) {
41         int v = edge[i].v;
42         if(G[u][v] > dis) continue;
43         if(!vis[v]) {
44             vis[v] = true;
45             if(cnt[v] < maxn) {
46                 love[v][++cnt[v]] = u;
47                 return true;
48             }
49             for(int j = 1; j <= cnt[v]; ++j) {
50                 if(dfs(love[v][j])) {
51                     love[v][j] = u;
52                     return true;
53                 }
54             }
55         }
56     }
57     return false;
58 }
59 
60 bool solve(int d) {
61     dis = d;
62     rep1(i, m) cnt[i] = 0;
63     Rep1(i, m+1, nm) {
64         rep1(j, m) vis[j] = false;
65         if(!dfs(i)) return false;
66     }
67     return true;
68 }
69 
70 int main() {
71     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
72     cin >> m >> n >> maxn;
73     nm = n+m;
74     num = 0;
75     rep1(i, nm) head[i] = -1;
76     rep1(i, nm) rep1(j, nm) cin >> G[i][j];
77     rep1(k, nm) {
78         rep1(i, nm) {
79             if(G[i][k]) rep1(j, nm) if(G[k][j]) if(!G[i][j] || G[i][k]+G[k][j] < G[i][j]) {
80                 G[i][j] = G[i][k] + G[k][j];
81             }
82         }
83     }
84     vector<int> v;
85     Rep1(i, m+1, nm) {
86         Rep1(j, 1, m) if(G[i][j]) add(i, j), v.push_back(G[i][j]);
87     }
88     sort(v.begin(), v.end());
89     int l = 0, r = unique(v.begin(), v.end()) - v.begin()-1;
90     int mi, ans;
91     while(l <= r) {
92         mi = (l+r)>>1;
93         if(solve(v[mi])) ans = v[mi], r = mi-1;
94         else l = mi+1;
95     }
96     cout << ans << "
";
97     return 0;
98 }

View Code

// poj 3189

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-11-04 23:50:39
 7  * @LastEditTime: 2019-11-05 00:27:17
 8  */
 9 #include<cstdio>
10 using namespace std;
11 const int MAXN = 1000+5;
12 const int MAXM = 20+5;
13 const int MAXE = MAXN*MAXM;
14 
15 int num;
16 int head[MAXN];
17 struct node {
18     int v, w, next;
19 } edge[MAXE];
20 
21 inline void add(int x, int y, int w) {
22     edge[num].v = y;
23     edge[num].w = w;
24     edge[num].next = head[x];
25     head[x] = num++;
26 }
27 
28 int n, m;
29 int G[MAXN][MAXM];
30 int maxn[MAXM];
31 
32 int cnt[MAXM];
33 int love[MAXM][MAXN];
34 bool vis[MAXM];
35 
36 bool dfs(int u, int l, int r) {
37     for(int i = head[u]; i != -1; i = edge[i].next) {
38         int v = edge[i].v;
39         if(edge[i].w < l || edge[i].w > r) continue;
40         if(!vis[v]) {
41             vis[v] = true;
42             if(cnt[v] < maxn[v]) {
43                 love[v][++cnt[v]] = u;
44                 return true;
45             }
46             for(int j = 1; j <= cnt[v]; ++j) {
47                 if(dfs(love[v][j], l, r)) {
48                     love[v][j] = u;
49                     return true;
50                 }
51             }
52         }
53     }
54     return false;
55 }
56 
57 bool solve(int l, int r) {
58     for(int i = 1; i <= m; ++i) cnt[i] = 0;
59     for(int i = 1; i <= n; ++i) {
60         for(int j = 1; j <= m; ++j) vis[j] = false;
61         if(!dfs(i, l, r)) return false;
62     }
63     return true;
64 }
65 
66 int main() {
67     scanf("%d%d", &n, &m);
68     num = 0;
69     for(int i = 1; i <= n; ++i) head[i] = -1;
70     for(int i = 1; i <= n; ++i) {
71         for(int j = 1; j <= m; ++j) {
72             scanf("%d", &G[i][j]);
73             add(i, G[i][j], j);
74         }
75     }
76     for(int i = 1; i <= m; ++i) scanf("%d", &maxn[i]);
77     int l = 1, r = m;
78     int mid, ans;
79     while(l <= r) {
80         bool flag = false;
81         mid = (l+r)>>1;
82         for(int i = 1; i+mid-1<=m; ++i) {
83             if(solve(i, i+mid-1)) ans = mid, flag = true;
84             if(flag) break;
85         }
86         if(flag) r = mid-1;
87         else l = mid+1;
88     }
89     printf("%d
", ans);
90     return 0;
91 }

View Code

// hdu 2255

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 const int MAXN = 300+5;
 6 
 7 int n;
 8 int w[MAXN][MAXN];
 9 int cx[MAXN], cy[MAXN];
10 
11 int love[MAXN];
12 bool visx[MAXN], visy[MAXN];
13 
14 bool dfs(int u) {
15     visx[u] = true;
16     for(int v = 1; v <= n; ++v) {
17         if(!visy[v] && cx[u] + cy[v] == w[u][v]) {
18             visy[v] = true;
19             if(!love[v] || dfs(love[v])) {
20                 love[v] = u;
21                 return true;
22             }
23         }
24     }
25     return false;
26 }
27 
28 int KM() {
29     for(int i = 1; i <= n; ++i) love[i] = 0;
30     for(int i = 1; i <= n; ++i) {
31         while(1) {
32             for(int j = 1; j <= n; ++j) visx[j] = visy[j] = false;
33             if(dfs(i)) break;
34             int d = INF;
35             for(int j = 1; j <= n; ++j) {
36                 if(visx[j]) {
37                     for(int k = 1; k <= n; ++k) {
38                         if(!visy[k]) d = min(d, cx[j]+cy[k]-w[j][k]);
39                     }
40                 }
41             }
42             //if(d == INF) return -1;
43             for(int i = 1; i <= n; ++i) {
44                 if(visx[i]) cx[i] -= d;
45                 if(visy[i]) cy[i] += d;
46             }
47         }
48     }
49     int ans = 0;
50     for(int i = 1; i <= n; ++i) {
51         ans += w[love[i]][i];
52     }
53     return ans;
54 }
55 
56 int main() {
57     while(scanf("%d", &n) == 1) {
58         for(int i = 1; i <= n; ++i) {
59             int d = 0;
60             for(int j = 1; j <= n; ++j) {
61                 scanf("%d", &w[i][j]);
62                 d = max(d, w[i][j]);
63             }
64             cx[i] = d;
65             cy[i] = 0;
66         }
67         printf("%d
", KM());
68     }
69     return 0;
70 }

View Code

// hdu 3488

 1 /*
 2  * @Promlem: 
 3  * @Time Limit: ms
 4  * @Memory Limit: k
 5  * @Author: pupil-XJ
 6  * @Date: 2019-11-05 20:59:41
 7  * @LastEditTime: 2019-11-05 22:20:49
 8  */
 9 #include<cstdio>
10 #include<algorithm>
11 #include<set>
12 using namespace std;
13 const int INF = 0x3f3f3f3f;
14 const int MAXN = 200+5;
15 
16 int n, m;
17 int w[MAXN][MAXN];
18 int cx[MAXN], cy[MAXN];
19 
20 int love[MAXN];
21 bool visx[MAXN], visy[MAXN];
22 
23 bool dfs(int u) {
24     visx[u] = true;
25     for(int v = 1; v <= n; ++v) {
26         if(!visy[v] && cx[u] + cy[v] == w[u][v]) {
27             visy[v] = true;
28             if(!love[v] || dfs(love[v])) {
29                 love[v] = u;
30                 return true;
31             }
32         }
33     }
34     return false;
35 }
36 
37 int KM() {
38     for(int i = 1; i <= n; ++i) love[i] = 0;
39     for(int i = 1; i <= n; ++i) {
40         while(1) {
41             for(int j = 1; j <= n; ++j) visx[j] = visy[j] = false;
42             if(dfs(i)) break;
43             int b = INF;
44             for(int j = 1; j <= n; ++j) {
45                 if(visx[j]) {
46                     for(int k = 1; k <= n; ++k) {
47                         if(!visy[k]) b = min(b, cx[j] + cy[k] - w[j][k]);
48                     }
49                 }
50             }
51             for(int j = 1; j <= n; ++j) {
52                 if(visx[j]) cx[j] -= b;
53                 if(visy[j]) cy[j] += b;
54             }
55         }
56     }
57     int ans = 0;
58     for(int i = 1; i <= n; ++i) {
59         ans += w[love[i]][i];
60     }
61     return -ans;
62 }
63 
64 int main() {
65     int T;
66     scanf("%d", &T);
67     while(T--) {
68         scanf("%d%d", &n, &m);
69         for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) w[i][j] = -INF;
70         int x, y, v;
71         set<int> xx[MAXN];
72         for(int i = 0; i != m; ++i) {
73             scanf("%d%d%d", &x, &y, &v);
74             if(-v > w[x][y]) w[x][y] = -v, xx[x].insert(v);
75         }
76         for(int i = 1; i <= n; ++i) {
77             cx[i] = -*xx[i].begin();
78             cy[i] = 0;
79         }
80         printf("%d
", KM());
81     }
82     return 0;
83 }

View Code

// URAL 1099

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-11-06 13:06:21
  7  * @LastEditTime: 2019-11-06 19:30:09
  8  */
  9 #include<cstdio>
 10 #include<queue>
 11 #include<set>
 12 using namespace std;
 13 const int MAXN = 222+5;
 14 const int MAXE = 2*222*222+5;
 15 
 16 int num;
 17 int head[MAXN];
 18 struct node {
 19     int v, next;
 20 } edge[MAXE];
 21 
 22 inline void add(int x, int y) {
 23     edge[num] = (node){y, head[x]};
 24     head[x] = num++;
 25 }
 26 
 27 int n, m;
 28 int love[MAXN];
 29 int vis[MAXN], fa[MAXN], pre[MAXN];
 30 int tim, dfn[MAXN];
 31 queue<int> q;
 32 
 33 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
 34 
 35 inline int LCA(int u, int v) {
 36     ++tim; u = find(u), v = find(v);
 37     while(dfn[u] != tim) {
 38         dfn[u] = tim;
 39         u = find(pre[love[u]]);
 40         if(v) swap(u, v);
 41     }
 42     return u;
 43 }
 44 
 45 inline void Blossom(int x, int y, int lca) {
 46     while(find(x) != lca) {
 47         pre[x] = y, y = love[x];
 48         if(vis[y] == 2) vis[y] = 1, q.push(y);
 49         if(find(x) == x) fa[x] = lca;
 50         if(find(y) == y) fa[y] = lca;
 51         x = pre[y];
 52     }
 53 }
 54 
 55 bool Aug(int s) {
 56     for(int i = 1; i <= n; ++i) fa[i] = i, vis[i] = pre[i] = 0;
 57     while(!q.empty()) q.pop();    
 58     q.push(s);
 59     vis[s] = 1;
 60     while(!q.empty()) {
 61         int u = q.front();
 62         q.pop();
 63         for(int i = head[u]; i != -1; i = edge[i].next) {
 64             int v = edge[i].v;
 65             if(find(u) == find(v) || vis[v] == 2) continue;
 66             if(!vis[v]) {
 67                 vis[v] = 2;
 68                 pre[v] = u;
 69                 if(!love[v]) {
 70                     for(int x = v, lst; x; x = lst) {
 71                         lst = love[pre[x]];
 72                         love[x] = pre[x];
 73                         love[pre[x]] = x;
 74                     }
 75                     return true;
 76                 }
 77                 //else
 78                 vis[love[v]] = 1;
 79                 q.push(love[v]);
 80             }
 81             else {
 82                 int lca = LCA(u, v);
 83                 Blossom(u, v, lca);
 84                 Blossom(v, u, lca);
 85             }
 86         }
 87     }
 88     return false;
 89 }
 90 
 91 int solve() {
 92     int ans = 0;
 93     tim = 0;
 94     for(int i = 1; i <= n; ++i) love[i] = 0;
 95     for(int i = 1; i <= n; ++i) {
 96         if(!love[i] && Aug(i)) ++ans;
 97     }
 98     return ans;
 99 }
100 
101 int main() {
102     scanf("%d", &n);
103     int num = 0;
104     for(int i = 1; i <= n; ++i) head[i] = -1;
105     int x, y;
106     while(scanf("%d%d", &x, &y) == 2) {
107         add(x, y); add(y, x);
108     }
109     printf("%d
", solve()*2);
110     set<int> dict;
111     for(int i = 1; i <= n; ++i) {
112         if(!dict.count(i) && love[i]) {
113             printf("%d %d
", i, love[i]);
114             dict.insert(i);
115             dict.insert(love[i]);
116         }
117     }
118     return 0;
119 }

View Code