Cod sursa(job #2600695)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 13 aprilie 2020 09:28:55
Problema Critice Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

const int N = 1001;
vector < pair < int, int > > graph[N];
queue < int > q;
int C[N][N], F[N][N], sol[N], tata[N];
bool viz[N], viz1[N], muchie[N];
int n;

bool bfs ( int start ){
    for ( int i = 1; i <= n; i++ )
        viz[i] = tata[i] = 0;
    viz[start] = 1;
    q.push ( start );
    while ( !q.empty ( ) ){
        int node = q.front ( );
        q.pop ( );
        for ( int i = 0; i < graph[node].size ( ); i++ ){
            int new_node = graph[node][i].first;
            if ( viz[new_node] == 0 && F[node][new_node] < C[node][new_node] ){
                viz[new_node] = 1;
                q.push ( new_node );
                tata[new_node] = node;
            }
        }
    }
    return viz[n];
}

void bfs2 ( int start ){
    viz1[start] = 1;
    q.push ( start );
    while ( !q.empty ( ) ){
        int node = q.front ( );
        q.pop ( );
        for ( int i = 0; i < graph[node].size ( ); i++ ){
            int new_node = graph[node][i].first;
            if ( viz1[new_node] == 0 && F[new_node][node] < C[new_node][node] ){
                viz1[new_node] = 1;
                q.push ( new_node );
            }
        }
    }
}

int main()
{   int m, i, x, y, k = 0, z;
    f >> n >> m;
    for ( i = 1; i <= m; i++ ){
        f >> x >> y >> z;
        C[x][y] = C[y][x] = z;
        graph[x].push_back ( { y, i } );
        graph[y].push_back ( { x, i } );
    }
    while ( bfs ( 1 ) == 1 ){
        for ( i = 0; i < graph[n].size ( ); i++ ){
            int node = graph[n][i].first;
            if ( viz[node] == 0 || F[node][n] == C[node][n] )
                continue;
            int Min = C[node][n] - F[node][n];
            while ( node != 1 ){
                Min = min ( Min, C[tata[node]][node] - F[tata[node]][node] );
                node = tata[node];
            }
            node = graph[n][i].first;
            F[node][n] += Min;
            F[n][node] -= Min;
            while ( node != 1 ){
                F[tata[node]][node] += Min;
                F[node][tata[node]] -= Min;
                node = tata[node];
            }
        }
    }
    bfs2 ( n );
    for ( i = 1; i <= n; i++ ){
        for ( int j = 0; j < graph[i].size ( ); j++ ){
            int node = graph[i][j].first;
            int ang = graph[i][j].second;
            if ( ( ( viz[i] == 1 && viz1[node] == 1 ) || ( viz1[i] == 1 && viz[node] == 1 ) ) && muchie[ang] == 0 ){
                sol[++k] = graph[i][j].second;
                muchie[ang] = 1;
            }
        }
    }
    g << k << '\n';
    for ( i = 1; i <= k; i++ )
        g << sol[i] << '\n';
    return 0;
}