Cod sursa(job #3190527)

Utilizator RadushCordunianu Radu Radush Data 7 ianuarie 2024 17:55:30
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;
#define dim 1002
ifstream fin("harta.in");
ofstream fout("harta.out");

int bfs(int s,int d,vector<vector<int>>& cap,vector<vector<int>>& flux,vector<vector<int>>& graf,vector<int>& t) {
    deque<int> deq;
    vector<int> viz(d+1,0);

    t.assign(d+1,0);

    deq.push_back(s);
    viz[s]=1;

    while (!deq.empty()){
        int nod=deq.front();
        deq.pop_front();
        if (nod==d)
            break;
        for (auto vec:graf[nod]) {
            if (!viz[vec] && cap[nod][vec]-flux[nod][vec]>0) {
                    deq.push_back(vec);
                    t[vec]=nod;
                    viz[vec]=1;
                }
        }
    }
    if (t[d]!=0)
        return 1;
    return 0;
}

int edmondKarp(int s,int d,vector<vector<int>>& cap,vector<vector<int>>& flux,vector<vector<int>>& graf) {
    int flow=0;
    int mn;
    vector<int> t;

    while (bfs(s,d,cap,flux,graf,t)){
        mn=INT_MAX;
        int i=d;
        while (i!=0) {
            if (cap[t[i]][i]-flux[t[i]][i]<mn)
                mn=cap[t[i]][i]-flux[t[i]][i];
            i=t[i];
        }

        i=d;
        while (i!=0) {
            flux[t[i]][i]+=mn;
            flux[i][t[i]]-=mn;
            i=t[i];
        }
        flow+=mn;
    }
    return flow;
}

int main(){
    int n,s,d;
    s=0;
    fin>>n;
    d=2*n+1;

    vector<vector<int>> cap(dim,vector<int>(dim,0)),flux(dim,vector<int>(dim,0)),graf(dim,vector<int>());
    vector<int> t;

    for (int i=1;i<=n;i++) {
        int x,y;
        fin>>x>>y;
        int k=n+i;

        graf[s].push_back(i);
        graf[k].push_back(d);
        cap[s][i]=x;
        cap[k][d]=y;
    }

    for (int i=1;i<=n;i++)
        for (int j=n+1;j<=2*n;j++)
            if (i!=(j-n)){
                graf[i].push_back(j);
                graf[j].push_back(i);
                cap[i][j]=1;
            }

    fout<<edmondKarp(s,d,cap,flux,graf)<<"\n";

    for (int i=1;i<=n;i++)
        for (int j=n+1;j<=2*n;j++) {
            if (flux[i][j]==1)
                fout<<i<<" "<<j-n<<endl;
        }
    return 0;
}