# Cod sursa(job #225136)

Utilizator Data 30 noiembrie 2008 14:44:28 Cuplaj maxim in graf bipartit Ascuns cpp done 2.33 kb
``````#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "cuplaj.in";
const char oname[] = "cuplaj.out";

#define MAXN  20005
#define FOR(i, a, b)  for (int i = (int)(a); i <= (int)(b); ++ i)

struct list {
int node, cap, flow;
list *nxt, *dup;
} ;

typedef list* plist;

plist adj[MAXN], edge[MAXN];    int n, m, q[MAXN], sel[MAXN], src, sink;

void alloc_edge(plist &nou, plist &dup, int i, int j)
{
nou = new list, dup = new list;
nou->node = j, dup->node = i;
nou->dup = dup, dup->dup = nou;
}

{
FILE *fi = fopen(iname, "r");
int cnt_edges, x, y;
plist nou, dup;

fscanf(fi, "%d %d %d", &n, &m, &cnt_edges);
for (; cnt_edges --; )
{
fscanf(fi, "%d %d", &x, &y);
alloc_edge(nou, dup, x, y + n);
nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
}
fclose(fi);

src = 0;
FOR (i, 1, n) {
alloc_edge(nou, dup, src, i);
nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
}
sink = n+m+1;
FOR (i, n + 1, n + m) {
alloc_edge(nou, dup, i, sink);
nou->cap = 1, nou->flow = dup->cap = dup->flow = 0;
}
}

int BFS(const int src, const int sink)
{
int h, t;
plist it;

memset(sel, 0, sizeof(sel));

edge[src] = 0;
for (sel[q[h = t = 0] = src] = 1; h <= t; ++ h)
{
for (it = adj[q[h]]; it; it = it->nxt)
if ((it->cap - it->flow) > 0 && !sel[it->node])
{
sel[q[++ t] = it->node] = 1;
edge[it->node] = it;
if (it->node == sink)
{
for (it = edge[sink]; it; it = edge[it->dup->node])
it->flow ++, it->dup->flow --;
return 1;
}
}
}
return 0;
}

int main(void)
{
int cuplaj = 0;
while (BFS(src, sink))  cuplaj ++;

FILE *fo = fopen(oname, "w");
fprintf(fo, "%d\n", cuplaj);
FOR (i, 1, n)
{
for (plist it = adj[i]; it; it = it->nxt)
if (it->flow == 1)
fprintf(fo, "%d %d\n", i, it->node - n);
}
fclose(fo);

return 0;
}
``````