Cod sursa(job #2642523)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 15 august 2020 19:25:07
Problema Traseu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <bits/stdc++.h>
#define Nmax 603
using namespace std;

ifstream f("traseu.in");
ofstream g("traseu.out");

int n,p,q,m,e,c,S,D,mn[Nmax],cst,ans,NR[Nmax],ant[Nmax],fw[Nmax][Nmax],C[Nmax][Nmax],IN[Nmax],OUT[Nmax];
bool inQ[Nmax];
vector<int> v[Nmax];

void belman(){
    memset(mn,0x3f,sizeof(mn));
    memset(ant,0xff,sizeof(ant));
    vector<int> H;
    H.push_back(S);
    mn[S] = 0;
    for (int i=0;i<H.size();i++){
        int nod = H[i];
        inQ[nod] = 0;
        for (int i = 0; i < v[nod].size(); i++){
            int it = v[nod][i];
            if (!fw[nod][it]) continue;
            if (mn[it]>mn[nod]+C[nod][it]){
                mn[it] = mn[nod] + C[nod][it];
                ant[it] = nod;
                if (!inQ[it]){
                    H.push_back(it);
                    inQ[it] = 1;
                }
            }
        }
    }
}

bool flow(){
    if (mn[D]>1e9) return 0;

    int nod = D;
    while (nod!=S){
        cst += C[ant[nod]][nod];
        fw[ant[nod]][nod] = 0;
        fw[nod][ant[nod]] = 1;
        nod = ant[nod];
    }
    ans++;

    return 1;
}

#define INF 9999999

int main()
{
    f >> n >> m;

    int aa = 0;
    for (int i=1;i<=m;i++){
        f >> p >> q >> c;
        q += n;
        v[p].push_back(q);
        fw[p][q] = INF;
        C[p][q] = c;
        v[q].push_back(p);
        fw[q][p] = 0;
        C[q][p] = -c;
        IN[q-n]++;
        OUT[p]++;
        aa += c;
    }

    for (int i=1;i<=n;i++){
        v[i+n].push_back(i);
        fw[i+n][i] = INF;
        C[i+n][i] = 0;
        v[i].push_back(i+n);
        fw[i][i+n] = INF;
        C[i][i+n] = 0;
    }

    S = 2 * n + 1;
    D = 2 * n + 2;


    for (int i=1;i<=n;i++){
        v[S].push_back(i);
        fw[S][i] = max(0, IN[i] - OUT[i]);
        C[S][i] = 0;
    }

    for (int i=n+1;i<=n+n;i++){
        v[i].push_back(D);
        fw[i][D] = max(0, OUT[i-n] - IN[i-n]);
        C[i][D] = 0;
    }

//    for (int i=1;i<=n+n+2;i++){
//        for (int j =0;j<v[i].size();j++){
//            cout << i << ' ' << v[i][j] << ' ' << fw[i][v[i][j]] << ' ' << C[i][v[i][j]] << '\n';
//        }
//    }

    belman();
    while(flow()){
        belman();
    }

    g<<cst + aa<<'\n';

    return 0;
}