hdu2389 Rain on your Parade
题解1.构二分图。
2.匈牙利算法超时（O（VE））
3.用Hopcroft-Carp算法（O（sqrt（V）E))
算法讲解
算法模板
AC code
#include <bits/stdc++.h>typedef long long LL;using namespace std;const int maxn = 3010;const int INF = 0x3f3f3f3f;bool g[maxn][maxn];bool vis[maxn];int dx[maxn],dy[maxn];int Mx[maxn],My[maxn];int dis;int GM[maxn][2];int GN[maxn][2];int speed[maxn];double _time;int M,N;bool bfs(int n,int m){dis = INF;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));queue <int> que;for(int i = 0; i < n; i++){if(Mx[i] == -1){que.push(i);dx[i] = 0;}}while(!que.empty()){int u = que.front();que.pop();if(dx[u] > dis) break;for(int v = 0; v < m; v ++){if(g[u][v] && dy[v] == -1){dy[v] = dx[u] + 1;if(My[v] == -1) dis = dy[v];else {dx[My[v]] = dy[v] + 1;que.push(My[v]);}}}}return dis != INF;}bool dfs(int u,int m){for(int v = 0; v < m; v++){if(g[u][v] && !vis[v] && dy[v] == dx[u] + 1){vis[v] = true;if(My[v] != -1 && dy[v] == dis) continue;if(My[v] == -1 || dfs(My[v],m)){My[v] = u;Mx[u] = v;return true;}}}return false;}int Max_match(int n,int m){int all = 0;memset(Mx,-1,sizeof(Mx));memset(My,-1,sizeof(My));while(bfs(n,m)){memset(vis,false,sizeof(vis));for(int i = 0; i < n; i++)if(Mx[i] == -1 && dfs(i,m))all++;}return all;}
