# Cod sursa(job #2758604)

Utilizator Data 11 iunie 2021 15:58:28 Cc 100 cpp-64 done Arhiva de probleme 2.02 kb
``````#include <bits/stdc++.h>
#define DIM 300
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
deque <int> c;
int capacitate[DIM][DIM],flux[DIM][DIM],cst[DIM][DIM],viz[DIM],t[DIM],dist[DIM];
int n,i,j,x,sursa,dest;

int bellmanFord (int sursa, int dest){
for (int i=sursa;i<=dest;i++){
dist[i] = INF;
viz[i] = 0;
t[i] = -1;
}
c.clear();
c.push_back(sursa);
dist[sursa] = 0;
viz[sursa] = 1;
while (!c.empty()){
int nod = c.front();
c.pop_front();
viz[nod] = 0;

for (auto vecin : L[nod]){
if (flux[nod][vecin] < capacitate[nod][vecin] && dist[nod] + cst[nod][vecin] < dist[vecin]){
dist[vecin] = dist[nod] + cst[nod][vecin];
t[vecin] = nod;
if (!viz[vecin]){
c.push_back(vecin);
viz[vecin] = 1;
}}}}

return dist[dest] != INF;
}

int main (){

ifstream cin ("cc.in");
ofstream cout ("cc.out");

cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
cin>>x;
L[i].push_back(j+n);
L[j+n].push_back(i);
cst[i][j+n] = x;
cst[j+n][i] = -x;
capacitate[i][j+n] = 1;
}

sursa = 0, dest = 2*n+1;

for (i=1;i<=n;i++){
L[sursa].push_back(i);
L[i].push_back(sursa);
capacitate[sursa][i] = 1;

L[i+n].push_back(dest);
L[dest].push_back(i+n);
capacitate[i+n][dest] = 1;
}

long long sol = 0;
while (bellmanFord(sursa,dest)){
int x = dest, dif = INF;
while (t[x] != -1){
dif = min (dif,capacitate[t[x]][x] - flux[t[x]][x]);
x = t[x];
}

x = dest;
while (t[x] != -1){
flux[t[x]][x] += dif;
flux[x][t[x]] -= dif;

sol += 1LL * dif * cst[t[x]][x];

x = t[x];
}

}

cout<<sol;

return 0;
}
``````