Pagini recente » Cod sursa (job #247814) | Borderou de evaluare (job #247804) | Cod sursa (job #2467201)
#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,m,x,y,z,c[1010],rasp,p,u,flux[1010][1010],T[1010],r[1010][1010];
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()){
int nod=n;
m=INT_MAX;
while(nod!=1){
m=min(m,r[T[nod]][nod]-flux[T[nod]][nod]);
nod=T[nod];
}
nod=n;
while(nod!=1){
flux[T[nod]][nod]+=m;
flux[nod][T[nod]]-=m;
nod=T[nod];
}
rasp+=m;
}
fout<<rasp;
return 0;
}