Cod sursa(job #2616497)

Utilizator claudiu7761Claudiu Mitrofan claudiu7761 Data 18 mai 2020 18:26:14
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
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 in[110];
int out[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 >> out[i] >> in[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] = out[i];
        c[100 + i][100 + n + 1] = in[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;
}