Cod sursa(job #2975105)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 5 februarie 2023 14:19:59
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.15 kb
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

ifstream cin("harta.in");
ofstream cout("harta.out");

class Graph
{

private:
    struct muchie
    {
        int to,ind,cap,flow;
    };
const int INF = 1 << 30;
int n,s,t;
vector<vector<muchie>> vecini;
vector<int> rem,dist;

bool bfs()
{
    fill(dist.begin(),dist.end(),INF);
    dist[s] = 0; queue<int> q; q.push(s);
    while(!q.empty())
        {
            int v = q.front() ; q.pop();
            for(auto it : vecini[v])
                {
                    if(dist[it.to] != (INF)) continue;
                    if(!(it.cap - it.flow)) continue;
                    dist[it.to] = dist[v] + 1;
                    q.push(it.to);
                }
        }

    return dist[t] != (INF);
}

int dfs(int nod,int f)
{
    if(nod == t)
        return f;

    for(int &h = rem[nod] ; h < vecini[nod].size() ; h++)
        {
            muchie &m = vecini[nod][h];
            if(dist[nod] + 1 != dist[m.to]) continue;
            int remcap = m.cap - m.flow;
            if(!remcap) continue;
            int pos = dfs(m.to,min(f,remcap));
            if(pos > 0)
                {
                    m.flow += pos;
                    vecini[m.to][m.ind].flow -= pos;
                    return pos;
                }
        }

    return 0;
}

public:
    Graph(int _n,int _s,int _t)
    {
        n = _n,s = _s,t = _t;
        vecini.resize(n + 1);
        rem.resize(n + 1,0);
        dist.resize(n + 1);
    }

    void add(int a,int b,int c)
    {
        vecini[a].push_back({b,vecini[b].size(),c,0});
        vecini[b].push_back({a,vecini[a].size() - 1,0,0});
       // vecini[b].push_back({a,vecini[a].size(),c,0});
        //vecini[a].push_back({b,vecini[b].size(),0,0});
    }

    void maxflow()
    {
        while(bfs())
            {
                fill(rem.begin(),rem.end(),0);
                int delta = dfs(s,INF);
                while(delta != 0)
                    {
                        delta = dfs(s,INF );
                    }
            }
    }

    void getans(int noduri)
    {
        vector<pair<int,int>> rez;
        for(int i = 1; i <= noduri ; i++)
            {
                for(auto it : vecini[i])
                    {
                        if(it.flow == 1)
                            {
                                rez.push_back({i,it.to - noduri});
                            }
                    }
            }

        cout << rez.size() << '\n';
        for(auto it : rez) cout << it.first << " " << it.second << '\n';

    }

};


int main()
{
    int n,m,a,b,c;
    cin >> n; int dest = 2 * n + 1;
    Graph g(dest,0,dest);
    for(int i = 1 ; i <= n ; i++)
        {
            cin >> a >> b;
            g.add(0,i,a);
            g.add(i + n,dest,b);
        }

    for(int i = 1; i <= n ; i++)
        {
            for(int j = 1; j <= n ; j++)
                {
                    if(i == j) continue;
                    g.add(i,j + n,1);
                }
        }

    g.maxflow();
    g.getans(n);

}