Cod sursa(job #2469397)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 6 octombrie 2019 23:43:41
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,i,cap[DIM][DIM],flux[DIM][DIM],t[DIM],fmin,fsol,nod,vecin,x,y,j;
bitset<DIM> f;
vector<int> L[DIM];
deque<int> q;
int bfs() {
    f.reset();
    f[0]=1;
    q.push_back(0);
    while (!q.empty()) {
        nod=q.front();
        for (int i=0;i<L[nod].size();i++) {
            int vecin=L[nod][i];
            if (f[vecin]==0&&cap[nod][vecin]>flux[nod][vecin]) {
                f[vecin]=1;
                q.push_back(vecin);
                t[vecin]=nod;
            }
        }
        q.pop_front();
    }
    return f[2*n+1];
}
int main() {
    fin>>n;
    for (i=1;i<=n;i++) {  //copiem nodurile grafului in 2 liste identice
        fin>>x>>y;        //si pe muchia dintre sursa si lista din stanga
        cap[0][i]=x;      //sau dintre destinatie si lista din dreapta
        L[0].push_back(i);//punem capacitatea egala cu cate drumuri ies/intra in oras
        L[i].push_back(0);
        cap[n+i][2*n+1]=y;
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i!=j) {
                cap[i][n+j]=1;      //ducem muchie de la fiecare nod din lista stanga
                L[i].push_back(n+j);//la celelalte din lista dreapta in afara de el
                L[n+j].push_back(i);
            }
    while (bfs()) {
        for (i=0;i<L[2*n+1].size();i++) {
            vecin=L[2*n+1][i];
            if (cap[vecin][2*n+1]-flux[vecin][2*n+1]>0&&f[vecin]==1) {
                fmin=cap[vecin][2*n+1]-flux[vecin][2*n+1];
                nod=vecin;
                while (nod!=0) {
                    fmin=min(fmin,cap[t[nod]][nod]-flux[t[nod]][nod]);
                    nod=t[nod];
                }
                fsol+=fmin;
                flux[vecin][2*n+1]+=fmin;
                flux[2*n+1][vecin]-=fmin;
                nod=vecin;
                while (nod!=0) {
                    flux[t[nod]][nod]+=fmin;
                    flux[nod][t[nod]]-=fmin;
                    nod=t[nod];
                }
            }
        }
    }
    fout<<fsol<<"\n";
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (flux[i][j]==1)
                fout<<i<<" "<<j-n<<"\n";
    return 0;
}