Cod sursa(job #3358914)

Utilizator Tudor_11Tudor Ioan Calin Tudor_11 Data 21 iunie 2026 22:14:40
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int v[101];
int w[101];
int cap[201][201];
int flux[201][201];
vector<int> v1[201];
int tata[201];
bool bfs(int n)
{
    vector<bool> aux(201,0);
    queue<int> Q;
    Q.push(0);
    aux[0]=1;
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for(auto it:v1[node])
        {
            if(aux[it]==0 && cap[node][it]-flux[node][it]>0)
            {
                aux[it]=1;
                tata[it]=node;
                Q.push(it);
            }
        }
    }
    return aux[2*n+1];
}
void calc_flux(int n)
{
    while(bfs(n))
    {
        int mn=INT_MAX;
        for(int i=2*n+1;i>0;i=tata[i])
        {
            mn=min(mn,cap[tata[i]][i]-flux[tata[i]][i]);
        }
        for(int i=2*n+1;i>0;i=tata[i])
        {
            flux[tata[i]][i]+=mn;
            flux[i][tata[i]]-=mn;
        }
    }
}
vector<pair<int,int>> ans;
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i]>>w[i];
        v1[0].push_back(i);
        v1[i].push_back(0);
        cap[0][i]=v[i];
        v1[2*n+1].push_back(i+n);
        v1[i+n].push_back(2*n+1);
        cap[i+n][2*n+1]=w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                v1[i].push_back(j+n);
                v1[j+n].push_back(i);
                cap[i][j+n]=1;
            }
        }
    }
    calc_flux(n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j && cap[i][j+n]-flux[i][j+n]==0)
            {
                ans.push_back({i,j});
            }
        }
    }
    fout<<ans.size()<<'\n';
    for(auto it:ans)
    {
        fout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}