Cod sursa(job #2469810)

Utilizator canmihaiCancescu Mihai canmihai Data 8 octombrie 2019 00:39:05
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>
#define DIM 5010
using namespace std;
vector<int> v[DIM];
queue<int> coada;
int n,m,x,y,z,minim,flux,nod,p,u,cap[DIM][DIM],sursa[DIM],a[DIM],v2[DIM][DIM],g;
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(){
    g=0;
    memset(a,0,DIM);
    a[0]=1;
    coada.push(0);
    while (!coada.empty()){
        nod=coada.front();
        for (int i=0;i<v[nod].size();i++){
            int vecin=v[nod][i];
            if (!a[vecin]&&cap[nod][vecin]>v2[nod][vecin]){
                coada.push(vecin);
                sursa[vecin]=nod;
                a[vecin]=1;
             //   if(vecin==n)
               //     g=1;
            }
        }
        coada.pop();

    }
    return a[2*n+1];
}

int main (){
    fin>>n;
    for (int i=1;i<=n;i++){
        fin>>x>>y;
        v[0].push_back(i);
        v[i].push_back(0);
        v[n+i].push_back(2*n+1);
        v[2*n+1].push_back(n+i);
        cap[0][i]=x;
        cap[n+i][2*n+1]=y;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j){
             cap[i][n+j]=1;
             v[i].push_back(n+j);
             v[n+j].push_back(i);
        }
        int sol;
    while (bfs()){
        for (int i=0;i<v[2*n+1].size();i++){
            p=v[2*n+1][i];
            if(cap[p][2*n+1]>v2[p][2*n+1]&&a[p]){
                minim=cap[p][2*n+1]-v2[p][2*n+1];
                u=p;
                while(u!=0){
                    minim=min(minim,cap[sursa[u]][u]-v2[sursa[u]][u]);
                    u=sursa[u];
                }
                flux+=minim;
                v2[p][2*n+1]+=minim,v2[2*n+1][p]-=minim;
                u=p;
                while(u!=0){
                    v2[sursa[u]][u]+=minim,v2[u][sursa[u]]-=minim;
                    u=sursa[u];
                }

            }

        }

    }
    fout<<flux<<"\n";
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<2*n+1;j++)
            if(v2[i][j]==1)
                fout<<i<<" "<<j-n<<"\n";

}