1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- // O(sqrt(n)*E)
- // Use : set G (adjacency list), set uN, then m = MaxMatch() and the result is in Mx and My
- const int MAXN = 1000; const int INF = 0x3f3f3f3f; vector<int>G [MAXN];
- int uN;
- int Mx[MAXN],My[MAXN]; int dx[MAXN],dy[MAXN]; int dis;
- bool used[MAXN];
- bool SearchP() {
- queue<int>Q;
- dis = INF;
- memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy));
- for(int i = 0 ; i < uN; i++)
- if(Mx[i] == -1) {
- Q.push(i);
- dx[i] = 0;
- }
- while(!Q.empty()) {
- int u = Q.front();
- Q.pop();
- if(dx[u] > dis) break;
- int sz = G[u].size();
- for(int i = 0;i < sz;i++) {
- int v = G[u][i];
- if(dy[v] == -1) {
- dy[v] = dx[u] + 1;
- if(My[v] == -1) dis = dy[v];
- else {
- dx[My[v]] = dy[v] + 1;
- Q.push( My[v ]);
- }
- }
- }
- }
- return dis != INF;
- }
- bool DFS(int u) {
- int sz = G[u].size();
- for(int i = 0;i < sz;i++) {
- int v = G[u][i];
- if(!used[v] && dy[v] == dx[u] + 1) {
- used[v] = true;
- if(My[v] != -1 && dy[v] == dis) continue;
- if(My[v] == -1 || DFS(My[v])) {
- My[v] = u; Mx[u] = v; return true;
- }
- }
- }
- return false;
- }
- int MaxMatch() {
- int res = 0;
- memset(Mx,-1,sizeof(Mx)); memset(My,-1,sizeof(My));
- while(SearchP()) {
- memset(used,false,sizeof(used));
- for(int i = 0;i < uN;i++)
- if(Mx[i] == -1 && DFS(i)) res++;
- }
- return res;
- }
|