Cod sursa(job #3187262)

Utilizator The_SupremacySus Impostor The_Supremacy Data 28 decembrie 2023 12:18:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1000;
vector<int>G[NMAX+5];
int capacitate[NMAX+5][NMAX+5];
int n;long long rez=0;int poz[NMAX+5];
queue<int>q;int dist[NMAX+5];
int DFS(int nod,int cap){
    if(nod==n||cap==0){return cap;}
    while(poz[nod]<G[nod].size()){
        int nod1=G[nod][poz[nod]];poz[nod]++;
        if(capacitate[nod][nod1]>0&&dist[nod1]==dist[nod]+1){
            int x=DFS(nod1,min(cap,capacitate[nod][nod1]));
            if(x!=0){
                capacitate[nod][nod1]-=x;
                capacitate[nod1][nod]+=x;return x;
            }
        }
    }
    return 0;
}
bool F_flux(){
    for(int i=1;i<=n;i++){
        poz[i]=0;dist[i]=INT_MAX;
    }
    dist[1]=0;
    q.push(1);
    while(!q.empty()){
        int nod=q.front();q.pop();
        for(int i=0;i<G[nod].size();i++){
            if(capacitate[nod][G[nod][i]]>0&&dist[G[nod][i]]>dist[nod]+1){
                dist[G[nod][i]]=dist[nod]+1;
                q.push(G[nod][i]);
            }
        }
    }
    if(dist[n]==INT_MAX){return 0;}
    long long adun=0;
    while(1){
        int ceva=DFS(1,INT_MAX);
        if(ceva==0){break;}adun+=ceva;
    }
    if(adun==0){return 0;}
    rez+=adun;return 1;
}
int main()
{
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    int a,b;fin>>n;
    for(int i=1;i<=n;i++){
        fin>>a>>b;
        capacitate[1][i+1]=a;
        G[1].push_back(i+1);G[i+1].push_back(1);
        capacitate[n+1+i][2*n+2]=b;
        G[2*n+2].push_back(n+1+i);
        G[n+1+i].push_back(2*n+2);
    }
    for(int i=2;i<=n+1;i++){
        for(int j=n+2;j<=2*n+1;j++){
            if((i-1)!=(j-n-1)){
                capacitate[i][j]=1;
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    n=2*n+2;
    while(1){
        if(F_flux()==0){break;}
    }
    int cnt=0;n-=2;n/=2;
    for(int i=2;i<=n+1;i++){
        for(int j=n+2;j<=2*n+1;j++){
            if((i-1)!=(j-n-1)){
                if(capacitate[i][j]==0){
                    cnt++;
                }
            }
        }
    }
    fout<<cnt<<'\n';
    for(int i=2;i<=n+1;i++){
        for(int j=n+2;j<=2*n+1;j++){
            if((i-1)!=(j-n-1)){
                if(capacitate[i][j]==0){
                    fout<<i-1<<" "<<j-n-1<<'\n';
                }
            }
        }
    }
    return 0;
}