Cod sursa(job #2982327)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 19 februarie 2023 22:25:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define INF 0x3f3f3f3f
const int N = 205;
int n, x, y, flow, mflow;
int c[N][N], parent[N];
bool visited[N];
bool bfs()
{
    queue<int> q;
    memset(parent, 0, sizeof(parent));
    memset(visited, false, sizeof(visited));

    q.push(0);
    visited[0] = true;
    parent[0] = -1;
    while(!q.empty()) {
        int currentNode = q.front();
        q.pop();
        
        if (currentNode == 2*n+1)
            return true;

        for (int i=1;i<=2*n+1;i++){
            if (!visited[i] && c[currentNode][i] > 0) {
                q.push(i);
                visited[i] = true;
                parent[i] = currentNode;
            }
        }
    }
    return false;
}
void EdmondsKarp()
{
    while(bfs()) {
        for (int i=1;i<=n;i++) {
            if (visited[n+i] && c[n+i][2*n+1] > 0) {
                flow = INF;
                parent[2*n+1] = n+i;

                for (int node=2*n+1;node!=0;node=parent[node])
                    flow = min(flow, c[parent[node]][node]);
                if (flow == 0)
                    continue;

                for (int node=2*n+1;node!=0;node=parent[node]) {
                    c[parent[node]][node] -= flow;
                    c[node][parent[node]] += flow;
                }
                mflow += flow;
            }
        }
    }
}
int main()
{
    fin >> n;
    for (int i=1;i<=n;i++){
        fin >> x >> y;
        c[0][i] = x;
        c[i+n][2*n+1] = y;
        for (int j=1;j<=n;j++){
            if (i != j)
                c[i][n+j] = 1;
        }
    }

    EdmondsKarp();
    fout << mflow << '\n';
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (c[i][n+j] == 0 && i != j){
                fout << i << ' ' << j << '\n';
            }
        }
    }
    return 0;
}