Cod sursa(job #2334323)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 2 februarie 2019 15:06:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

int n,i,j,dist[210],tata[210],cap[210][210];
vector<pair<int,int> > ans;
vector<int> v[210];

bool djikstra()
{
    memset(dist,127,sizeof(dist));
    memset(tata,  0,sizeof(tata));
    priority_queue<pair<int,int> > q;
    q.push({0,0});
    dist[0]=0;
    while(q.size())
    {
        int cst=-q.top().first,x=q.top().second;
        if(x==2*n+1)break;
        q.pop();
        if(cst>dist[x])continue;
        for(auto it:v[x])
            if(cap[x][it])
                if(dist[it]>dist[x]+1)
                {
                    dist[it]=dist[x]+1;
                    tata[it]=x;
                    q.push({-dist[it],it});
                }
    }
    if(dist[2*n+1]>=1e9)return 0;
    int flx=1e9;
    for(int x=2*n+1;x;x=tata[x])
        flx=min(flx,cap[tata[x]][x]);
    for(int x=2*n+1;x;x=tata[x])
        cap[tata[x]][x]-=flx,cap[x][tata[x]]+=flx;
    return 1;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        int a,b;
        f>>a>>b;
        v[0].push_back(i);
        v[i].push_back(0);
        cap[0][i]=a;
        v[i+n].push_back(2*n+1);
        v[2*n+1].push_back(i+n);
        cap[i+n][2*n+1]=b;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                cap[i][j+n]=1;
            }
//    for(i=0;i<=2*n+1;i++)
//    {
//        g<<i<<": ";
//        for(auto it:v[i])
//            g<<it<<','<<cap[i][it]<<' ';
//        g<<'\n';
//    }
    for(;djikstra(););
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                if(!cap[i][j+n])
                    ans.push_back({i,j});
    g<<ans.size()<<'\n';
    for(auto it:ans)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}