Cod sursa(job #3196378)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 23 ianuarie 2024 19:21:05
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
using pii = pair<int,int>;
const int inf = 1e9;
struct edge
{
    int y , cap , flow , ridx;
};
vector <edge> g[202];
int source , sync , n , a , b , sz[202], level[202] , ef[202];
queue<int>q;
bool bfs()
{
    memset(level,0,sizeof(level));
    memset(ef,0,sizeof(ef));
    q.push(source);
    level[source] = 1;
    while(!q.empty())
    {
        a = q.front(); q.pop();
        for(auto it : g[a])
        {
            if(!level[it.y] && it.cap > it.flow)
            {
                level[it.y] = level[a]+1;
                q.push(it.y);
            }
        }
    }
    return(level[sync]>0);
}
int aug(int x , int flow)
{
    if(x == sync) return flow;
    for(; ef[x] < sz[x] ; ef[x]++)
    {
        edge it = g[x][ef[x]];
        if(level[it.y]==level[x]+1 && it.cap>it.flow)
        {
            int nf = aug(it.y,min(flow,it.cap-it.flow));
            if(!nf) continue;
            g[x][ef[x]].flow += nf;
            g[it.y][g[x][ef[x]].ridx].flow -= nf;
            return nf;
        }
    }
    return 0;
}
int main()
{
    cin >> n;
    source = 0;
    sync = n+n+1;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> a >> b;
        g[0].push_back({i,a,0,sz[i]++});
        g[i].push_back({0,0,0,sz[0]++});
        g[n+i].push_back({sync,b,0,sz[sync]++});
        g[sync].push_back({n+i,0,0,sz[n+i]++});
        for(int j = 1 ; j <= n ; ++j)
        {
            if(j == i) continue;
            g[i].push_back({j+n,1,0,sz[j+n]++});
            g[j+n].push_back({i,0,0,sz[i]++});
        }
    }
    while(bfs())
    {
        while(true)
        {
            if(!aug(source,inf)) break;
        }
    }
    vector<pii>ans;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(auto it : g[i])
        {
            if(!it.cap || it.cap-it.flow>0) continue;
            ans.push_back({i,it.y-n});
        }
    }
    cout << ans.size() << '\n';
    for(auto it : ans)
    {
        cout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}