Cod sursa(job #2747750)

Utilizator GligarEsterabadeyan 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;
}