Cod sursa(job #2447001)

Utilizator CharacterMeCharacter Me CharacterMe Data 11 august 2019 14:48:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;
int n, i, j, k, maxflow, cap;
int past[208], flow[208][208], cnt[208];
queue<int> q;
void read();
void solve();
void write();
bool bfs();
int dfs(int node, int val);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("harta.in", "r", stdin);
    scanf("%d", &n);
    for(i=1; i<=n; ++i){
        int in, out;
        scanf("%d%d", &in, &out);
        flow[0][i]=out;
        flow[i+n][2*n+1]=in;
        k=k+in+out;
        cap=cap+out;
    }
    k/=2;
    return;
}
void solve(){
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j) if(i!=j)flow[i][j+n]=1;
    while(bfs());
    return;
}
void write(){
    freopen("harta.out", "w", stdout);
    printf("%d\n", k);
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j) if(i!=j && i!=0 && j!=2*n+1 && !flow[i][j+n]) printf("%d %d\n", j, i);
}
bool bfs(){
    q.push(0);
    for(i=0; i<=2*n+1; ++i) past[i]=cnt[i]=0;
    cnt[0]=1;
    while(!q.empty()){
        int init=q.front(); q.pop();
        for(int next=0; next<=2*n+1; ++next) if(flow[init][next]){
            if(!cnt[next]){
                cnt[next]=cnt[init]+1;
                past[next]=init;
                q.push(next);
            }
        }
    }
    if(!cnt[2*n+1]) return false;
    int elim=1, pos=2*n+1;
    while(pos){
        flow[past[pos]][pos]-=elim;
        flow[pos][past[pos]]+=elim;
        pos=past[pos];
    }
    return true;
}