Cod sursa(job #2695317)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 12 ianuarie 2021 14:41:44
Problema Critice Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("critice.in");
ofstream fout("critice.out");

int n,m;
vector<int> firstNode, secondNode;
unordered_map <int, int> edges[1001];
int parent[1005];

int bfs()
{
    int s = 1;
    int t = n;
    memset(parent, 0, sizeof(parent));

    queue <int> q;
    q.push(s);
    parent[s] = -1;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (auto nextNode : edges[node])
        {
            if (!parent[nextNode.first] && nextNode.second > 0)
            {
                q.push(nextNode.first);
                parent[nextNode.first] = node;

            }
        }


    }
    return parent[t];

}


void dfs (int s, bool visited[])
{
    visited[s] = true;
    for (auto& nextNode : edges[s])
        if (nextNode.second && !visited[nextNode.first])
            dfs(nextNode.first, visited);
}


void solve ()
{

    int node, path_flow;
    bool visited[n + 5];
    memset(visited, 0, sizeof(visited));

    while (bfs())
    {
        for (auto& nextNode : edges[n])
            if (parent[nextNode.first] && edges[nextNode.first][n])
            {
                node = n;
                parent[n] = nextNode.first;
                while (node != 1)
                {
                    path_flow = min(path_flow, edges[parent[node]][node]);
                    node = parent[node];
                }
                node = n;
                if (path_flow > 0)
                    while (node != 1)
                    {
                        edges[parent[node]][node] -= path_flow;
                        edges[node][parent[node]] += path_flow;
                        node = parent[node];
                    }
            }
    }

    dfs(1, visited);
    int ans = 0;
    for (int i = 1; i <= m; i++)
        if (visited[firstNode[i]] != visited[secondNode[i]])
            ans ++;

    fout << ans << "\n";

    for (int i = 1; i<= m; i++)
        if (visited[firstNode[i]] != visited[secondNode[i]])
            fout << i << "\n";


}



int main()
{
    fin >> n >> m;
    firstNode.resize(m + 5);
    secondNode.resize(m + 5);
    for(int i = 1; i <= m; ++i)
    {
        int c;
        fin >> firstNode[i] >> secondNode[i] >> c;
        edges[firstNode[i]][secondNode[i]] = c;
        edges[secondNode[i]][firstNode[i]] = c;
    }


    solve();





    return 0;
}