Cod sursa(job #2456785)

Utilizator bogdi1bogdan bancuta bogdi1 Data 15 septembrie 2019 14:27:16
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include<queue>
using namespace std;
int cap[205][205];
int flow[205][205];
vector<int> g[205];
int parcbfs[205];
queue<int> q;
bool viz[205];
struct Solutie
{
    int x,y;
} sol[10005];
int in[105];
int out[105];
bool bfs(int x, int y)
{
    int i;
    q.push(x);
    for(i=1; i<=y; i++)
        viz[i]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(u!=y)
            for(i=0; i<g[u].size(); i++){
                int v=g[u][i];
                if(viz[v]==0 && flow[u][v]<cap[u][v]){
                    viz[v]=1;
                    q.push(v);
                    parcbfs[v]=u;
                }
            }
    }
    return viz[y]==1;
}
void detflow(int n){
    int i,flu,maxflow=0;
    while(bfs(n-1, n)){
        for(i=0; i<g[n].size(); i++){
            int v=g[n][i];
            if(cap[v][n]>flow[v][n]){
                parcbfs[n]=v;
                flu=2000000000;
                for(int nod=n; nod!=n-1; nod=parcbfs[nod])
                    flu=min(flu, cap[parcbfs[nod]][nod]-flow[parcbfs[nod]][nod]);
                for(int nod=n; nod!=n-1; nod=parcbfs[nod]){
                    flow[parcbfs[nod]][nod]+=flu;
                    flow[nod][parcbfs[nod]]-=flu;
                }
                maxflow+=flu;
            }
        }
    }
}
int main()
{   freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    int n,i,j;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        scanf("%d%d", &out[i], &in[i]);
    for(i=1; i<=n; i++)
        for(j=n+1; j<=2*n; j++){
            if(j!=i+n){
            g[i].push_back(j);
            g[j].push_back(i);
            cap[i][j]=1;
            }
        }
    for(i=1; i<=n; i++){
        g[2*n+1].push_back(i);
        g[i].push_back(2*n+1);
        g[2*n+2].push_back(n+i);
        g[n+i].push_back(2*n+2);
        cap[2*n+1][i]=out[i];
        cap[n+i][2*n+2]=in[i];
    }
    detflow(2*n+2);
    for(i=1; i<=n; i++){
        for(j=0; j<g[i].size(); j++)
            if(flow[i][g[i][j]]==1 && g[i][j]<=2*n){
                sol[++sol[0].x].x=i;
                sol[sol[0].x].y=((g[i][j]<=n)?g[i][j]:g[i][j]-n);
            }
    }
    printf("%d\n", sol[0].x);
    for(i=1; i<=sol[0].x; i++)
        printf("%d %d\n", sol[i].x, sol[i].y);
    return 0;
}