Cod sursa(job #3142912)

Utilizator alexddAlexandru Dima alexdd Data 25 iulie 2023 17:15:00
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int INF = 1e9;
int n;
int din[105];
int dout[105];
vector<int> con[205];
int capacity[205][205];
int prec[205];
void add_edge(int x, int y, int w)
{
    con[x].push_back(y);
    con[y].push_back(x);
    capacity[x][y]=w;
}
int bfs()
{
    for(int i=1;i<=2*n+2;i++)
        prec[i]=0;
    prec[2*n+1]=-1;
    deque<pair<int,int>> dq;
    dq.push_back({2*n+1,INF});
    while(!dq.empty())
    {
        int nod = dq.front().first;
        int flow = dq.front().second;
        dq.pop_front();
        if(nod==2*n+2)
            return flow;
        for(auto adj:con[nod])
        {
            if(prec[adj]==0 && capacity[nod][adj]>0)
            {
                prec[adj]=nod;
                dq.push_back({adj,min(flow,capacity[nod][adj])});
            }
        }
    }
    return 0;
}
void maxflow()
{
    int flow=0;
    while(1)
    {
        int x = bfs();
        if(x==0)
            break;
        int cur=2*n+2;
        while(cur!=2*n+1)
        {
            capacity[prec[cur]][cur]-=x;
            capacity[cur][prec[cur]]+=x;
            cur=prec[cur];
        }
        flow+=x;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j && capacity[i][j+n]==0)
                fout<<i<<" "<<j<<"\n";
}
signed main()
{
    fin>>n;
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        fin>>dout[i]>>din[i];
        add_edge(2*n+1,i,dout[i]);
        add_edge(i+n,2*n+2,din[i]);
        tot+=din[i];
    }
    fout<<tot<<"\n";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                add_edge(i,j+n,1);
    maxflow();
}