Pagini recente » Borderou de evaluare (job #2468801) | Cod sursa (job #2468700)
#include <fstream>
#include <vector>
#include <climits>
#include <bitset>
#define X first
#define Y second
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,i,minim,x,y,z,c[1010],rasp,p,u,flux[1010][1010],T[1010],r[1010][1010],m;
vector<int> L[1010];
bitset<1010> f;
int bfs(){
f.reset();
p=u=c[1]=f[1]=1;
while(p<=u){
int nod=c[p];
for(int i=0;i<L[nod].size();i++){
int vec=L[nod][i];
if(f[vec]==0&&(r[nod][vec]-flux[nod][vec]>0)){
f[vec]=1;
T[vec]=nod;
c[++u]=vec;
}
}
p++;
}
return f[n];
}
int main(){
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y>>z;
L[x].push_back(y);
L[y].push_back(x);
r[x][y]=z;
}
while(bfs()){
for(int i=0;i<L[n].size();i++){
int nod=L[n][i];
if(r[nod][n]>flux[nod][n]&&f[nod]==1){
minim=r[nod][n]-flux[nod][n];
while(nod!=1){
minim=min(minim,r[T[nod]][nod]-flux[T[nod]][nod]);
nod=T[nod];
}
nod=L[n][i];
flux[nod][n]+=minim;
flux[n][nod]-=minim;
while(nod!=1){
flux[T[nod]][nod]+=minim;
flux[nod][T[nod]]-=minim;
nod=T[nod];
}
rasp+=minim;
}
}
}
fout<<rasp;
return 0;
}