Cod sursa(job #2663079)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 25 octombrie 2020 12:02:47
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <cstring>
#define dim 210
using namespace std;
vector <int> a[dim];
queue<int> c;
int f[dim];
int t[dim];
int cost[dim][dim];
int flux[dim][dim];
int iesire[dim];
int intrare[dim];
int i,j,n,m,Min,sol,nod,vecin;

int bfs() {
    for (;!c.empty();c.pop())
    memset (f,0,sizeof(f));
    c.push(0);
    f[0]=1;
    while (!c.empty()) {
        int nod=c.front();
        for (int i=0;i<a[nod].size();i++) {
            int vecin=a[nod][i];
            if (cost[nod][vecin]>flux[nod][vecin]&&f[vecin]==0) {
                f[vecin]=1;
                c.push(vecin);
                t[vecin]=nod;
                if (vecin==2*n+1) {
                    return 1;
                }
            }
        }
        c.pop();
    }
    return 0;
}

int main() {
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>iesire[i]>>intrare[i];
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            if (i==j) continue;
            a[i].push_back(n+j);
            a[n+j].push_back(i);
            cost[i][n+j]=1;
        }
    }
    for (i=1;i<=n;i++) {
        a[0].push_back(i);
        a[i].push_back(0);
        cost[0][i]=intrare[i];
    }
    for (i=n+1;i<=2*n;i++) {
        a[2*n+1].push_back(i);
        a[i].push_back(2*n+1);
        cost[i][2*n+1]=iesire[i-n];
    }
    while (bfs()) {
        t[0]=-1;
        Min=INT_MAX;
        for (i=2*n+1;t[i]!=-1;i=t[i]) {
            Min=min(Min,cost[t[i]][i]-flux[t[i]][i]);
        }
        sol+=Min;
        for (i=2*n+1;t[i]!=-1;i=t[i]) {
            flux[t[i]][i]+=Min;
            flux[i][t[i]]-=Min;
        }
    }
    fout<<sol<<"\n";
    for (nod=1;nod<=n;nod++) {
        for (i=0;i<a[nod].size();i++) {
            vecin=a[nod][i];
            if (flux[nod][vecin]==1&&vecin!=nod+n) {
                fout<<nod<<" "<<vecin-n<<"\n";
            }
        }
    }
    return 0;
}