Pagini recente » Borderou de evaluare (job #1945749) | Cod sursa (job #23850) | Borderou de evaluare (job #1307443) | Rezultatele filtrării | Cod sursa (job #2761648)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
#define nil 0
#define inf INT_MAX
#define maxn 10001
vector<int>tav(maxn+1);
vector<int>pair_v(maxn+1,nil);
vector<int>pair_u(maxn+1,nil);
int n,m,e;
vector<vector<int> >adj(maxn);
ifstream be("cuplaj.in");
ofstream ki("cuplaj.out");
bool bfs()
{
queue<int>q;
for(int sz=1;sz<=m;sz++)
{
if(pair_u[sz]==nil)
{
tav[sz]=0;
q.push(sz);
}
else
tav[sz]=inf;
}
tav[nil]=inf;
while(!q.empty())
{
int v=q.front();
q.pop();
if(tav[v]<tav[nil]){
for(auto sz:adj[v])
{
if(tav[pair_v[sz]]==inf)
{
tav[pair_v[sz]]=tav[v]+1;
q.push(pair_v[sz]);
}
}
}
}
return (tav[nil]!=inf);
}
bool dfs(int start)
{
if(start!=nil){
for(auto sz:adj[start])
{
if(tav[pair_v[sz]]==tav[start]+1)
{
if(dfs(pair_v[sz]))
{
pair_v[sz]=start;
pair_u[start]=sz;
return true;
}
}
}
tav[start]=inf;
return false;
}
return true;
}
int hopcroftKarp()
{
int res=0;
while(bfs())
{
for(int i=1;i<=m;i++)
{
if(pair_u[i]==nil && dfs(i))
res++;
}
}
return res;
}
int main()
{
be>>m>>n>>e;
for(int i=1;i<=e;i++)
{
int x,y;
be>>x>>y;
adj[x].push_back(y);
}
ki<<hopcroftKarp()<<"\n";
for(int i=1;i<=m;i++)
if(pair_u[i]!=0)
ki<<i<<" "<<pair_u[i]<<"\n";
return 0;
}