Cod sursa(job #996932)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 12 septembrie 2013 22:26:37
Problema Critice Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define NM 1010

using namespace std;

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

int N, M;
int Cap[NM][NM], Flow[NM][NM];
int A[10*NM], B[10*NM];
vector<int> G[NM];
vector<int> ANS;
queue<int> Q;
int T[NM];
bool PathS[NM], PathD[NM];

bool BF ()
{
    memset(PathS, 0, sizeof(PathS));
    PathS[1]=1;
    Q.push(1);

    int node;
    vector<int>::iterator it;

    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();

        if (node==N) continue;

        for (it=G[node].begin(); it!=G[node].end(); ++it)
            if (PathS[*it]==0 && Cap[node][*it]>Flow[node][*it])
            {
                T[*it]=node;
                PathS[*it]=1;
                Q.push(*it);
            }
    }

    return PathS[N];
}

void DF (int node, bool Path[])
{
    Path[node]=1;
    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
        if (Path[*it]==0 && Cap[node][*it]>Flow[node][*it] && Cap[*it][node]>Flow[*it][node])
            DF(*it, Path);
}

int main ()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        Cap[a][b]=Cap[b][a]=c;
        G[a].push_back(b);
        G[b].push_back(a);
        A[i]=a;
        B[i]=b;
    }

    while (BF())
        for (vector<int>::iterator it=G[N].begin(); it!=G[N].end(); ++it)
            if (PathS[*it] && Flow[*it][N]!=Cap[*it][N])
            {
                T[N]=*it;
                int FMIN=0x3f3f3f3f;

                for (int i=N; i!=1; i=T[i])
                    FMIN=min(FMIN, Cap[T[i]][i]-Flow[T[i]][i]);

                for (int i=N; i!=1; i=T[i])
                {
                    Flow[T[i]][i]+=FMIN;
                    Flow[i][T[i]]-=FMIN;
                }
            }

    memset(PathS, 0, sizeof(PathS));
    memset(PathD, 0, sizeof(PathD));

    DF(1, PathS);
    DF(N, PathD);



    for (int i=1; i<=M; i++)
        if ((PathS[A[i]]==1 && PathD[B[i]]==1) || (PathS[B[i]]==1 && PathD[A[i]]==1))
            ANS.push_back(i);

    g << ANS.size() << '\n';
    for (int i=0; i<ANS.size(); i++)
        g << ANS[i] << '\n';

    f.close();
    g.close();

    return 0;
}