Cod sursa(job #3188106)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 1 ianuarie 2024 17:48:45
Problema Flux maxim Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("maxflow.in");
ofstream G("maxflow.out");
vector<short> g[1001];
int i,j,n,y,l,k,e[1001][1001],b[1001],c[1001];
int main()
{
    for(F>>n>>k;F>>i>>j>>k;g[i].push_back(j),g[j].push_back(i),e[i][j]=k);
    for(;;) {
        for(memset(b,0,sizeof b),j=c[0]=c[1]=1;j<=c[0]&&!b[n];++j)
        	for(k=c[j],l=g[k].size(),i=0;i<l;!b[g[k][i]]&&e[k][g[k][i]]?b[c[++c[0]]=g[k][i]]=k:0,++i);
        if(!b[n])
            return G<<y,0;
        for(k=g[n].size(),i=0;i<k;++i)
        	if(b[g[n][i]]&&e[g[n][i]][n]) {
            	for(l=2e5,b[n]=j=k=g[n][i];j>1;l=min(l,e[b[j]][j]),j=b[j]);
            	for(l=min(l,e[k][n]),y+=l,j=n;j>1;e[b[j]][j]-=l,e[j][b[j]]+=l,j=b[j]);
        	}
    }
}