Cod sursa(job #2960199)

Utilizator Paul12PPaul Dumitru Paul12P Data 3 ianuarie 2023 18:48:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define INF 9999999
vector<vector<int>>adj;
int capacity[202][202];
int tata[202];
int n;
int bfs(){
    queue<pair<int,int>> q;
    for(int i=0;i<=2*n+1;i++){
        tata[i]=-1;
    }
    q.push({0,INF});
    tata[0]=-2;
    while(!q.empty()){
        int u=q.front().first;
        int flow=q.front().second;
        q.pop();
        for(auto v:adj[u]){
            if(tata[v]==-1 && capacity[u][v]>0){
                tata[v]=u;
                int new_flow=min(flow,capacity[u][v]);
                if(v==2*n+1)
                    return new_flow;
                q.push({v,new_flow});
            }
        }
    }
    return 0;
}
int main() {
    int x,y,i,j,flow,maxflow=0;
    ifstream cin("harta.in");
    ofstream cout("harta.out");
    cin>>n;
    adj.resize(2*n+2);
    for(i=1;i<=n;i++){
        cin>>x>>y;
        adj[0].push_back(i);
        adj[i].push_back(0);
        capacity[0][i]=x;
        capacity[n+i][2*n+1]=y;
        adj[n+i].push_back(2*n+1);
        adj[2*n+1].push_back(n+i);
        for(j=n+1;j<=2*n;j++){
            if(j-i==n)
                continue;
            capacity[i][j]=1;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
    while(flow=bfs()){
        maxflow+=flow;
        int cur=2*n+1;
        while(cur!=0){
            int prev=tata[cur];
            capacity[cur][prev]+=flow;
            capacity[prev][cur]-=flow;
            cur=prev;
        }
    }
    cout<<maxflow<<'\n';
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
            if(capacity[j][i]==1){
                cout<<i<<" "<<j-n<<'\n';
            }

    cin.close();
    cout.close();
}