Cod sursa(job #2469761)

Utilizator radugnnGone Radu Mihnea radugnn Data 7 octombrie 2019 22:43:01
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <iostream>
#include <bitset>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
bitset<DIM> U;
vector<int> L[DIM];
int C[DIM][DIM],F[DIM][DIM],T[DIM];
deque<int> q;
pair <int,int> sol[100010];
int n,m,i,x,y,z,flux,cp,p,mn,j,d,cnt;
int bfs(){
    int destinatie=0;
    U.reset();
    U[0]=1;
    q.push_back(0);
    while(!q.empty()){
        int nod=q.front();
        for(int i=0;i<L[nod].size();i++){
                int vecin=L[nod][i];
                if(U[vecin]==0 && C[nod][vecin]>F[nod][vecin]){
                    U[vecin]=1;
                    q.push_back(vecin);
                    T[vecin]=nod;
                    if(vecin==2*n+1)
                        destinatie=1;

                }

        }
        q.pop_front();
    }
    return destinatie;


}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        C[0][i]=x;
        C[n+i][2*n+1]=y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
    }
    for(i=1;i<=n;i++)
    for(j=n+1;j<=2*n;j++){
        if(j-i != n){
            L[i].push_back(j);
            L[j].push_back(i);
            C[i][j]=1;
        }
    }
    d=2*n+1;
    while(bfs()){
        for(i=0;i<L[d].size();i++){
            p=L[d][i];
                if(C[p][d] > F[p][d] && U[p]==1 ){
                mn=C[p][d]-F[p][d];
                cp=p;
                while(cp){
                    if(C[T[cp]][cp]-F[T[cp]][cp] < mn)
                       mn=C[T[cp]][cp]-F[T[cp]][cp];
                    cp=T[cp];
                }
                F[p][d] += mn;
                F[d][p] -= mn;
                cp=p;
                while(cp){
                    F[T[cp]][cp]+=mn;
                    F[cp][T[cp]]-=mn;
                    cp=T[cp];
                }
                }
        }
    }
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
            if(F[i][j]){
                sol[++cnt].first=i;
                sol[cnt].second=j-n;
            }
    fout<<cnt<<"\n";
    for(i=1;i<=cnt;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";



    return 0;
}