Cod sursa(job #2616506)

Utilizator claudiu7761Claudiu Mitrofan claudiu7761 Data 18 mai 2020 18:34:17
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");
vector<int> adj[210];
vector<int> sol[110];
int n;
int c[210][210];
int vin[110];
int vout[110];
int parent[110];

int bfs(int s,int d)
{
    queue<int> q;
    bool visited[1010];
    memset(visited, 0, sizeof (visited));
    q.push(s);
    parent[s]=s;
    int current;
    visited[0]=1;

    while(!q.empty()) {
        current=q.front();
        q.pop();

        if(current != d)
        for(int nextNode : adj[current])
        {

            if(!visited[nextNode] && c[current][nextNode])
            {
                visited[nextNode]=1;
                parent[nextNode]=current;
                q.push(nextNode);
            }
        }
    }
    return visited[d];
}

int main()
{

    in >> n;
    int i,j;
    for (i = 1; i <= n; i++)
        in >> vout[i] >> vin[i];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i != j)
            {
                c[i][100+j] = 1;
                adj[i].push_back(100 + j);
                adj[100 + j].push_back(i);
            }
    for (i = 1; i <= n; i++)
    {
        adj[0].push_back(i);
        adj[i].push_back(0);
        c[0][i] = vout[i];
        c[100 + i][100 + n + 1] = vin[i];
        adj[100 + i].push_back(100 + n + 1);
        adj[100 + n + 1].push_back(100 + i);
    }



    int current, maxim, flow = 0;
    while (bfs(0,100 + n + 1))
    {

        for (int i = 1; i <=n ; i++)
            if (parent[100 + i] && c[100 + i][100 + n + 1])
        {

            parent[100 + n + 1] = 100 + i;
            current = 100 + n + 1;
            maxim = 0x7fffffff;
            while (current != parent[current])
            {

                if (maxim > c[parent[current]][current])
                    maxim = c[parent[current]][current];
                current = parent[current];
            }

            flow += maxim;
            current = 100 + n + 1;
            while (current != parent[current])
            {
                c[current][parent[current]] += maxim;
                c[parent[current]][current] -= maxim;
                current = parent[current];
            }
        }
    }
    out << flow << '\n';
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (c[j+100][i])
                out << i << ' ' << j << '\n';
    in.close();
    out.close();
    return 0;
}