Cod sursa(job #2103772)

Utilizator Bodo171Bogdan Pop Bodo171 Data 10 ianuarie 2018 19:54:34
Problema Algola Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=2*2555;
vector<int> v[nmax];
char fl[nmax][nmax],c[nmax][nmax];
int q[nmax],prec[nmax];
int n,m,i,j,source,sink,timp,t,p,u,start,nod,x,sum,a,b,cap,flow,minfl;
int e(int loc,int timp)
{
    return (loc-1)*101+timp+1;
}
void add(int x,int y,int cap)
{
    c[x][y]=cap;
    v[x].push_back(y);
    v[y].push_back(x);
}
bool bfs()
{
    for(i=1;i<=sink;i++)
        prec[i]=0;
    prec[source]=-1;
    q[p=u=1]=source;
    while(p<=u)
    {
        start=q[p];p++;
        for(i=0;i<v[start].size();i++)
        {
            nod=v[start][i];
            if((!prec[nod])&&fl[start][nod]<c[start][nod])
            {
                prec[nod]=start;
                q[++u]=nod;
                if(nod==sink)
                    return 1;
            }
        }
    }
    return 0;
}
int main()
{
    ifstream f("algola.in");
    ofstream g("algola.out");
    f>>n>>m;
    source=e(n,50)+1;
    sink=source+1;
    for(i=1;i<=n;i++)
    {
        f>>x;
        add(source,e(i,0),x);
        sum+=x;
    }
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>cap;
        for(t=0;t<50;t++)
        {
            add(e(a,t),e(b,t+1),cap);
            add(e(b,t),e(a,t+1),cap);
        }
    }
    for(i=1;i<=n;i++)
        for(t=0;t<50;t++)
          add(e(i,t),e(i,t+1),50);
    add(e(1,0),sink,50);
    while(flow<sum)
    {
        while(bfs())
        {
            nod=sink;minfl=51;
            while(nod!=source)
            {
                minfl=min(minfl,c[prec[nod]][nod]-fl[prec[nod]][nod]);
                nod=prec[nod];
            }
            nod=sink;
            while(nod!=source)
            {
                fl[prec[nod]][nod]+=minfl;
                fl[nod][prec[nod]]-=minfl;
                nod=prec[nod];
            }
            flow+=minfl;
        }
        timp++;
        add(e(1,timp),sink,50);
    }
    g<<timp-1;
    return 0;
}