Cod sursa(job #3191564)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 9 ianuarie 2024 23:17:05
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");

int cap[205][205];
int in[105];
int out[105];
int t[205];
int source, sink;
vector <int> G[205];
queue < pair <int, int> > q;
int bfs(){
    while(!q.empty()) q.pop();
    memset(t,-1,sizeof t);
    q.push({source,1e9});
    while(!q.empty()){
        for(auto x : G[q.front().first]){
            if(t[x] == -1 && cap[q.front().first][x]){
                t[x] = q.front().first;
                int new_flow = min(q.front().second, cap[q.front().first][x]);
                if(x == sink) return new_flow;
                q.push({x,new_flow});
            }
        }
        q.pop();
    }
    return 0;
}
void edmonds_karp(){
    int flow = 0, new_flow;
    while(new_flow = bfs()){
        flow += new_flow;
        int e = sink;
        while(t[e] != -1){
            cap[t[e]][e] -= new_flow;
            cap[e][t[e]] += new_flow;
            e = t[e];
        }
    }
}
vector < pair <int, int> > sol;
int main()
{
    int n,i;
    fin >> n;
    source = 0;
    sink = 2 * n + 1;
    for(i = 1; i <= n; i++){
        fin >> out[i] >> in[i];
        G[source].push_back(i);
        G[n + i].push_back(sink);
        cap[source][i] = out[i];
        cap[n + i][sink] = in[i];
    }
    for(i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i != j){
                G[i].push_back(n + j);
                G[n + j].push_back(i);
                cap[i][n + j] = 1;
            }
        }
    }
    edmonds_karp();
    for(i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i != j && !cap[i][n + j]) sol.push_back({i,j});
        }
    }
    fout << sol.size() << "\n";
    for(auto x : sol) fout << x.first << " " << x.second << "\n";
    return 0;
}