1191: [HNOI2006]超级英雄Hero

分析：

　　二分+网络流，二分答案，网络流判断。

　　或者匈牙利，从1到n挨个匹配。

匈牙利：0ms

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cctype>
 4 
 5 const int N = 1010;
 6 
 7 struct Edge{
 8     int to,nxt;
 9     Edge() {}
10     Edge(int a,int b) {to = a,nxt = b;}
11 }e[1000100];
12 int head[N],match[N],tot;
13 bool vis[N];
14 int n,m;
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 i=head[u]; i; i=e[i].nxt) {
24         int v = e[i].to - m;
25         if (!vis[v]) {
26             vis[v] = true;
27             if (!match[v] || dfs(match[v])) {
28                 match[v] = u;
29                 return true;
30             }
31         }
32     }
33     return false;
34 }
35 int main () {
36     n = read(),m = read();
37     for (int i=1; i<=m; ++i) {
38         int x = read() + 1,y = read() + 1;
39         e[++tot] = Edge(x+m,head[i]);head[i] = tot;
40         e[++tot] = Edge(y+m,head[i]);head[i] = tot;
41     }
42     int ans = 0;
43     for (int i=1; i<=m; ++i) {
44         memset(vis,false,sizeof(vis));
45         if (dfs(i)) ans++;
46         else break;
47     }
48     printf("%d",ans);
49     return 0;
50 }

View Code

网络流：72ms

 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 = 5010;
11  
12 inline int read() {
13     int x = 0,f = 1;char ch=getchar();
14     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
15     for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
16     return x*f;
17 }
18 struct Edge{
19     int to,nxt,c;
20     Edge() {}
21     Edge(int x,int y,int z) {to = x,c = y,nxt = z;}
22 }e[100010];
23 int head[N],dis[N],cur[N],q[N],a[N],b[N];
24 int L,R,tot,S,T,n,m;
25  
26 void add_edge(int u,int v,int w) {
27     e[++tot] = Edge(v,w,head[u]);head[u] = tot;
28     e[++tot] = Edge(u,0,head[v]);head[v] = tot;
29 }
30 bool bfs() {
31     for (int i=1; i<=T; ++i) cur[i] = head[i],dis[i] = -1;
32     L = 1;R = 0;
33     q[++R] = S;
34     dis[S] = 0;
35     while (L <= R) {
36         int u = q[L++];
37         for (int i=head[u]; i; i=e[i].nxt) {
38             int v = e[i].to;
39             if (dis[v] == -1 && e[i].c > 0) {
40                 dis[v] = dis[u] + 1;
41                 q[++R] = v;
42                 if (v == T) return true;
43             }
44         }
45     }
46     return false;
47 }
48 int dfs(int u,int flow) {
49     if (u == T) return flow;
50     int used = 0,tmp;
51     for (int i=cur[u]; i; i=e[i].nxt) {
52         int v = e[i].to;
53         if (dis[v] == dis[u] + 1 && e[i].c > 0) {
54             tmp = dfs(v,min(flow-used,e[i].c));
55             if (tmp) {
56                 e[i].c -= tmp;e[i^1].c += tmp;
57                 used += tmp;
58                 if (used == flow) break;
59             }
60         }
61     }
62     if (used != flow) dis[u] = -1;
63     return used;
64 }
65 bool check(int x) {
66     memset(head,0,sizeof(head));
67     tot = 1;
68     S = x + n + 1,T = x + n + 2;
69     for (int i=1; i<=x; ++i) {   
70         add_edge(i+n,a[i],1);
71         add_edge(i+n,b[i],1);   
72         add_edge(S,i+n,1);      
73     }
74     for (int i=1; i<=n; ++i) add_edge(i,T,1);
75     int ans = 0;
76     while (bfs()) 
77     ans += dfs(S,1e9);
78     return ans==x;
79 }
80 int main() {
81     n = read(),m = read();
82     for (int i=1; i<=m; ++i) {
83         a[i] = read()+1,b[i] = read()+1;
84     }
85     int L = 1,R = m,ans = 1;
86     while (L <= R) {
87         int mid = (L + R) / 2;
88         if (check(mid)) ans = mid,L = mid + 1;
89         else R = mid - 1;
90     }
91     cout << ans;
92     return 0;
93 }

View Code