Участник:Easik/MATCHING

Материал из DISCOPAL
Перейти к: навигация, поиск

C \ gcc

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> /* bool */
 
#define MAX 100001
#define QUEUE_SIZE 1000
#define INF (int)1e10
 
int N, M, P;
int match[MAX], dist[MAX];
int G[MAX][QUEUE_SIZE];
int STARTS[MAX];
int ENDS[MAX];
 
int hopcroft_karp();
bool bfs();
bool dfs(int u);
 
 
int main() {
 
	int i;
    int u, v;
 
	scanf("%d %d %d", &N, &M, &P);
 
    for (i = 0; i < MAX; i++) {
 
        STARTS[i] = 0;
        ENDS[i] = 0;
 
    }
 
	for (i = 0; i < P; i++) {
 
        /* A cow that is matched to the bull */
        /* u in G1, v in G2 */
		scanf("%d %d", &u, &v);
 
		v += N;
 
        G[u][ENDS[u]++] = v;
        G[v][ENDS[v]++] = u;
 
	}
 
	printf("%d\n", hopcroft_karp());
 
	return 0;
 
}
 
 
int hopcroft_karp() {
 
    int i;
	int matching = 0;
 
	while (bfs()) {
 
		for (i = 1; i <= N; i++) {
 
			if ((match[i] == 0) && dfs(i)) {
 
				matching++;
 
            }
 
        }
 
    }
 
	return matching;
 
}
 
 
/* Breadth-first search */
bool bfs() {
 
	int i;
    int u, v;
    int len;
    int queue[MAX];  /* Won't shift all items when dequeue happens */
    int queue_front = 0, queue_back = 0;
 
	for (i = 1; i <= N; i++) {
 
        if (match[i] == 0) {
 
            dist[i] = 0;
            queue[queue_back++] = i;
 
		} else {
 
            dist[i] = INF;
 
        }
 
	}
 
	dist[0] = INF;
	while (queue_back - queue_front > 0) {
 
		u = queue[queue_front];
        queue_front++;
 
		if (u != 0) {
 
			len = ENDS[u] - STARTS[u];
 
			for (i = 0; i < len; i++) {
 
                v = G[u][i];
				if (dist[match[v]] == INF) {
 
					dist[match[v]] = dist[u] + 1;
                    queue[queue_back++] = match[v];
 
				}
 
			}
 
		}
 
	}
 
	return dist[0] != INF;
 
}
 
 
/* Depth-first search */
bool dfs(int u) {
 
	int i;
    int v, len;
 
	if (u != 0) {
 
		len = ENDS[u] - STARTS[u];
 
		for (i = 0; i < len; i++) {
 
			v = G[u][i];
 
			if (dist[u] + 1 == dist[match[v]]) {
 
                if (dfs(match[v])) {
 
					match[v] = u;
					match[u] = v;
					return true;
 
				}
 
			}
 
		}
 
		dist[u] = INF;
 
		return false;
 
	}
 
	return true;
 
}