Cod sursa(job #2241975)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 17 septembrie 2018 15:38:57
Problema Cuplaj maxim in graf bipartit Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 10005
#define inf 1e9
using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
int m, a,b, start, stop, cp[nmax][nmax], fx[nmax][nmax], viz[nmax], t[nmax];
vector <int> v[nmax];
queue  <int> q;

void citire()
{
    int k,i,j;
    start=0;
    f>>a>>b>>m;
    stop=a+b+1;
    {
        for(k=1; k<=m; k++)
        {
            f>>i>>j;
            j=a+j;
            v[i].push_back(j);
            v[j].push_back(i);
            cp[i][j]=1;
            v[start].push_back(i);
            v[i].push_back(0);
            cp[start][i]=1;
            v[j].push_back(stop);
            v[stop].push_back(j);
            cp[j][stop]=1;
        }
    }
}

int bfs()
{
    int j,nod;
    while(!q.empty()) q.pop();
    for(j=1; j<=stop; j++) viz[j]=0;
    // ma opresc inainte de a ajunge la nodul destinatie
    q.push(start);
    viz[start]=1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(j=0; j<v[nod].size(); j++)
            if(!viz[v[nod][j]] && fx[nod][v[nod][j]]<cp[nod][v[nod][j]])
            {
                q.push(v[nod][j]);
                viz[v[nod][j]]=1;
                t[v[nod][j]]=nod;
                if(v[nod][j]==stop)
                    return 1;
            }
    }
    return 0;
}

int flux()
{
    int fl=0, fmin, i, k;
    // cat timp gaseste drum de la sursa la destinatie
    while(bfs())
    {
        for(i=0; i<v[stop].size(); i++)
            if(viz[v[stop][i]] && cp[v[stop][i]][stop]>fx[v[stop][i]][stop])
            {
                fmin=inf;
                t[stop]=v[stop][i];
                for(k=stop; k!=start; k=t[k])
                    fmin=min(fmin, cp[t[k]][k]-fx[t[k]][k]);
                for(k=stop; k!=start; k=t[k])
                {
                    fx[t[k]][k]+=fmin;
                    fx[k][t[k]]-=fmin;
                }
                fl+=fmin;
            }
    }
    return fl;
}

void afis()
{
    int i,j;
    for(i=1; i<=a; i++)
        {for(j=a; j<=a+b; j++)
        cout<<fx[i][j]<<" ";
    cout<<endl;}cout<<endl;
}

int main()
{
    citire();
    g<<flux()<<"\n";
    int i,j;
    afis();
    for(i=1; i<=a; i++)
    for(j=a+1; j<=a+b; j++)
        if(fx[i][j] || fx[j][i])
        g<<i<<" "<<j-a<<"\n";
    return 0;
}