Cod sursa(job #2661154)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 21 octombrie 2020 15:00:34
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 105;
const int INF = (1<<29);
int f[NMAX][NMAX],c[NMAX][NMAX],tata[NMAX];
int n,N,x,y,z,rasp=0;
bool ver[NMAX];
vector <int> v[NMAX];
queue <int> q;
bool bfs(){
    for(int i=0;i<=N;i++) ver[i]=false;
    ver[0]=true;
    q.push(0);
    while(!q.empty()){
        int node=q.front();
        q.pop();
        for(int i=0;i<v[node].size();i++){
            int vecin=v[node][i];
            if(ver[vecin]==false and c[node][vecin]>f[node][vecin]){
                q.push(vecin);
                tata[vecin]=node;
                ver[vecin]=true;
            }
        }
    }
    if(ver[N]==true) return 1;
    return 0;
}
int main()
{
    fin >> n;
    N=2*n+1;
    for(int i=1;i<=n;i++){
        fin >> x >> y;
        v[0].push_back(i);
        v[i].push_back(0);
        c[0][i]=x;
        v[n+i].push_back(N);
        v[N].push_back(n+i);
        c[n+i][N]=y;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            v[i].push_back(n+j);
            v[n+j].push_back(i);
            c[i][n+j]=1;
        }
    }
    while(bfs()==true){
        for(int i=0;i<v[N].size();i++){
            int nod=v[N][i];
            if(ver[nod]==true and c[nod][N]>f[nod][N]){
                int minim=c[nod][N]-f[nod][N];
                int aux=nod;
                while(aux!=0){
                    int t=tata[aux];
                    if(c[t][aux]-f[t][aux]<minim)
                        minim=c[t][aux]-f[t][aux];
                    aux=tata[aux];
                }
                if(minim==0) continue;
                rasp+=minim;
                f[nod][N]+=minim;
                f[N][nod]-=minim;
                aux=nod;
                while(aux!=0){
                    int t=tata[aux];
                    f[t][aux]+=minim;
                    f[aux][t]-=minim;
                    aux=tata[aux];
                }
            }
        }
    }
    fout << rasp << '\n';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j+n]==1)
            fout << i << ' ' << j << '\n';
        }
    }
    return 0;
}