Cod sursa(job #2321451)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 16 ianuarie 2019 08:46:16
Problema Critice Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("critice.in");
ofstream g("critice.out");

int n,m,x,X[10010],Y[10010],c,i,t[1010],T[1010],cap[1010][1010],flux[1010][1010];
vector<int> ans,v[1010];
queue<int> Q;

bool BFS()
{
    t[1]=-1;
    for(i=2;i<=n;i++)t[i]=0;
    Q.push(1);
    while(Q.size())
    {
        x=Q.front();Q.pop();
        for(auto it:v[x])
        {
            if(t[it]>0||it==1)
                continue;
            if(flux[x][it]==cap[x][it])continue;
            t[it]=x;
            Q.push(it);
        }
    }
    if(!t[n])
        return 0;
    return 1;
}

void UPD()
{
    x=t[n];
    int flx=cap[x][n]-flux[x][n];
    while(t[x]!=-1)
    {
        flx=min(flx,cap[t[x]][x]-flux[t[x]][x]);
        x=t[x];
    }
    x=n;
    while(t[x]!=-1)
    {
        flux[t[x]][x]+=flx;
        flux[x][t[x]]-=flx;
        x=t[x];
    }
    return ;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>X[i]>>Y[i]>>c;
        cap[X[i]][Y[i]]=c;
        cap[Y[i]][X[i]]=c;
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    while(BFS())UPD();
//    for(i=1;i<=m;i++)
//        g<<X[i]<<' '<<Y[i]<<' '<<flux[X[i]][Y[i]]<<':'<<cap[X[i]][Y[i]]<<'\n';
    BFS();
    T[n]=-1;
    for(i=1;i<n;i++)T[i]=0;
    Q.push(n);
    while(Q.size())
    {
        x=Q.front();Q.pop();
        for(auto it:v[x])
        {
            if(T[it]>0||it==n)
                continue;
            if(flux[it][x]==cap[it][x])continue;
            T[it]=x;
            Q.push(it);
        }
    }
//    for(i=1;i<=n;i++)
//        cout<<t[i]<<' ';cout<<'\n';
//    for(i=1;i<=n;i++)
//        cout<<T[i]<<' ';cout<<'\n';
//    for(i=1;i<=n;i++)
//        cout<<X[i]<<' '<<Y[i]<<' '<<flux[X[i]][Y[i]]<<':'<<cap[X[i]][Y[i]]<<' '<<flux[Y[i]][X[i]]<<':'<<cap[Y[i]][X[i]]<<'\n';
    for(i=1;i<=m;i++)
        if((t[X[i]]&&T[Y[i]]&&cap[X[i]][Y[i]]==flux[X[i]][Y[i]])||(T[X[i]]&&t[Y[i]]&&cap[Y[i]][X[i]]==flux[Y[i]][X[i]]))
            ans.push_back(i);
    g<<ans.size()<<'\n';
    for(auto it:ans)
        g<<it<<'\n';
    return 0;
}