Cod sursa(job #2469052)

Utilizator DanutAldeaDanut Aldea DanutAldea Data 6 octombrie 2019 14:37:22
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <deque>
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int n,i,j,k,nod,vec,flux[205][205],c[205][205],t[205],m,cnt;
vector <int> l[205];
bitset <205> f;
deque <int> d;
pair<int,int> sol[10001];

bool bfs(){
    f.reset();
    d.push_back(0);
    f[0]=1;

    while(!d.empty()){
        nod=d.front();
        for(i=0;i<l[nod].size();i++){
            vec=l[nod][i];

            if(!f[vec] && c[nod][vec]-flux[nod][vec]>0){
                d.push_back(vec);
                t[vec]=nod;
                f[vec]=1;
            }
        }

        d.pop_front();
    }

    return f[n];
}

int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        l[0].push_back(i), l[i].push_back(0);
    for(i=n+1;i<=2*n;i++)
        l[2*n+1].push_back(i), l[i].push_back(2*n+1);
    for(i=1;i<=n;i++){
        fin>>j>>k;
        c[0][i]=j;
        c[i+n][2*n+1]=k;
    }

    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;
            }

    while(bfs()){
        for(i=0;i<l[2*n+1].size();i++){
            nod=l[2*n+1][i];
            if(f[nod] && c[nod][2*n+1]-flux[nod][2*n+1]>0){
                m=c[nod][2*n+1]-flux[nod][2*n+1];

                while(nod!=0){
                    m=min(m,c[t[nod]][nod]-flux[t[nod]][nod]);
                    nod=t[nod];
                }

                nod=l[2*n+1][i];
                flux[nod][2*n+1]+=m;
                flux[2*n+1][nod]-=m;

                while(nod!=0){
                    flux[t[nod]][nod]+=m;
                    flux[nod][t[nod]]-=m;
                    nod=t[nod];
                }
            }
        }
    }

    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
            if(flux[i][j]==1)
                sol[++cnt]=make_pair(i,j-n);

    fout<<cnt<<"\n";
    for(i=1;i<=cnt;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";


    return 0;
}