# Cod sursa(job #2529052)

Utilizator Data 22 ianuarie 2020 21:53:04 Cuplaj maxim in graf bipartit 50 cpp-64 done Arhiva educationala 2.17 kb
``````#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin ("cuplaj.in");
ofstream cout ("cuplaj.out");

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;

#define inf 10000000

int n, m, n1, n2;
VVI G, c, f;

bool bfs()
{
queue<int> Q;
Q.push(0);
VB viz = VB(n + 2);
int node, V;
while (!Q.empty())
{
node = Q.front();
Q.pop();
if (node == n + 1)return 1;
for (int i = 0; i < G[node].size(); ++ i)
{
V = G[node][i];
if (viz[V] || c[node][V] == f[node][V])continue;
viz[V] = 1;
Q.push(V);
}
}
return 0;
}
int main()
{
cin >> n1 >> n2 >> m;
n = n1 + n2;
G = VVI(n + 2);
c = VVI(n + 2, VI(n + 2));
f = VVI(n + 2, VI(n + 2));

int x, y;
while (m --)
{
cin >> x >> y;
G[x].push_back(y + n1);
G[y + n1].push_back(x);
c[x][y + n1] ++;
}

for (int i = 1; i <= n1; ++ i)
{
G[0].push_back(i);
G[i].push_back(0);
c[0][i] = 1;
}
for (int i = 1; i <= n2; ++ i)
{
G[n + 1].push_back(n1 + i);
G[n1 + i].push_back(n + 1);
c[n1 + i][n + 1] = 1;
}

int V, flow = 0, val;
while (bfs())
for (int i = 0; i < G[n + 1].size(); ++ i)
{
V = G[n + 1][i];
if (f[V][n + 1] == c[V][n + 1])continue;

val = inf;
for (int j = n + 1; j != 0; j = dad[j])

if (val)
for (int j = n + 1; j != 0; j = dad[j])
{