Cod sursa(job #2747750)
Utilizator | Esterabadeyan Hadi Gligar | Data | 29 aprilie 2021 16:48:56 |
---|---|---|---|
Problema | Cuplaj maxim in graf bipartit | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.05 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");
const int nmax=1000;
vector <int> g[2*nmax+2];
int f[2*nmax+2][2*nmax+2],t[2*nmax+2];
queue <int> q;
int main(){
int n,m,e;
fin>>n>>m>>e;
int ss=n+m;
for(int i=1;i<=e;i++){
int x,y;
fin>>x>>y;
y+=n;
g[x].push_back(y);
g[y].push_back(x);
f[x][y]=1;
}
for(int i=1;i<=n;i++){
g[0].push_back(i);
g[i].push_back(0);
f[0][i]=1;
}
for(int i=n+1;i<=ss;i++){
g[i].push_back(ss+1);
g[ss+1].push_back(i);
f[i][ss+1]=1;
}
int ok=1,sol=0;
ss++;
while(ok==1){
for(int i=1;i<=ss;i++){
t[i]=-1;
}
q.push(0);
while(q.empty()==0){
int x=q.front();
q.pop();
for(int i=0;i<int(g[x].size());i++){
int xn=g[x][i];
if(f[x][xn]>0&&t[xn]==-1){
t[xn]=x;
q.push(xn);
}
}
}
if(t[ss]!=-1){
ok=1;
for(int i=0;i<int(g[ss].size());i++){
int p=g[ss][i],mini=f[p][ss];
if(mini>0){
while(p!=0){
if(f[t[p]][p]<mini){
mini=f[t[p]][p];
}
p=t[p];
}
p=g[ss][i];
if(mini>0){
while(p!=0){
f[t[p]][p]-=mini;
f[p][t[p]]+=mini;
p=t[p];
}
f[g[ss][i]][ss]-=mini;
f[ss][g[ss][i]]+=mini;
sol+=mini;
}
}
}
}else{
ok=0;
}
}
fout<<sol<<"\n";
return 0;
}