Cod sursa(job #2952003)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 7 decembrie 2022 23:35:04
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.15 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int NMAX=205,INF=0x3F3F3F3F;///we want double the number of nodes,because we double them to create the bipartite graph
int n,x,y,c,maxx;
bool SCALING=0;///you can choose between having scaling and not having scaling
///it is better without scaling on edges with lower costs, but on high cost edges, scaling helps a lot
struct edge
{
    int node,flow,capacity,index;
};
vector<int>level,skip;
vector<pair<int,int>>no_of_edges;
vector<edge>graph[NMAX];
void read()
{
    f>>n;
    no_of_edges.resize(n+1);
    for(int i=1; i<=n; i++)
        f>>no_of_edges[i].first>>no_of_edges[i].second;
}
void create_graph()
{
    read();
    maxx=c=1;///because we do maximum matching in a bipartite graph
    for(int i=1; i<=n; i++)///add the edges between the sides, maximum number of edges - the edge from i to i+n
    {
        x=i;///the node on the left
        for(int j=1; j<=n; j++)
            if(j!=x)
            {
                y=j+n;///the node on the right
                graph[x].push_back({y,0,c,0});///to node,flow,capacity,index
                graph[y].push_back({x,0,0,0});///reverse edge:to node,flow,capacity,index
                graph[x].back().index=graph[y].size()-1;///index from adjacency list of y
                graph[y].back().index=graph[x].size()-1;///index from adjacency list of x
            }
    }
    for(int i=1; i<=n; i++)///add the edges from the source
    {
        x=2*n+1;///the source
        y=i;///the node on the left
        c=no_of_edges[i].first;///representing the number of edges which should start from i
        graph[x].push_back({y,0,c,0});///to node,flow,capacity,index
        graph[y].push_back({x,0,0,0});///reverse edge:to node,flow,capacity,index
        graph[x].back().index=graph[y].size()-1;///index from adjacency list of y
        graph[y].back().index=graph[x].size()-1;///index from adjacency list of x
    }
    for(int i=1; i<=n; i++)///add the edges to the terminal
    {
        x=i+n;///the node on the right
        y=2*n+2;///the terminal
        c=no_of_edges[i].second;///representing the number of edges which should end in i
        graph[x].push_back({y,0,c,0});///to node,flow,capacity,index
        graph[y].push_back({x,0,0,0});///reverse edge:to node,flow,capacity,index
        graph[x].back().index=graph[y].size()-1;///index from adjacency list of y
        graph[y].back().index=graph[x].size()-1;///index from adjacency list of x
    }
}
bool bfs(int s,int t,int limit)
{
    level.assign(2*n+3,-1);///because we do maximum matching in a bipartite graph and we have 2*n+2 nodes
    level[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int node=q.front();
        q.pop();
        for(edge& link:graph[node])
            if(link.capacity-link.flow>0 && level[link.node]==-1 && (!SCALING || link.capacity-link.flow>=limit))///if I can still push flow and the next node is not visited
            {
                level[link.node]=level[node]+1;
                q.push(link.node);
            }
    }
    return level[t]!=-1;///if t was visited it will return 1,otherwise 0
}
int dfs(int node,int t,int cur_flow)
{
    if(node==t)
        return cur_flow;
    for(; skip[node]<(int)graph[node].size(); skip[node]++) ///we start from the pointer we have for this node
    {
        int next=graph[node][skip[node]].node;
        edge& link=graph[node][skip[node]];///for simplicity
        if(link.capacity-link.flow>0 && level[node]+1==level[next])///if I can still push flow and the node is not visited and we only go forward
        {
            int bottleNeck=dfs(next,t,min(cur_flow,link.capacity-link.flow));
            if(bottleNeck>0)
            {
                link.flow+=bottleNeck;///update on the normal edge
                graph[next][link.index].flow-=bottleNeck;///update on the reverse edge
                return bottleNeck;
            }
        }
    }
    return 0;
}
int maxflow(int s,int t)
{
    int max_flow=0;
    skip.resize(2*n+3);///because we do maximum matching in a bipartite graph and we have 2*n+2 nodes
    for(int limit=SCALING ? (1<<(int(log2(maxx)))) : 1; limit>0; limit=limit/2)
        while(bfs(s,t,limit))
        {
            fill(skip.begin(),skip.end(),0);///for pruning dead ends
            for(int new_flow=dfs(s,t,INF); new_flow!=0; new_flow=dfs(s,t,INF))///as long as we can find a new path we increase the max_flow
                max_flow+=new_flow;
        }
    return max_flow;
}
void solve()
{
    g<<maxflow(2*n+1,2*n+2)<<'\n';///the number of edges
    for(int i=1; i<=n; i++)
        for(int j=0; j<(int)graph[i].size(); j++)///the last edge on graph[i] is the one from the source, which has the flow negative, so there is no problem if we keep it
            if(graph[i][j].flow==1)///we have used the edge from i to graph[i][j].node
                g<<i<<' '<<graph[i][j].node-n<<'\n';///we subtract n because we should print the normal node
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    create_graph();
    solve();
    return 0;
}