Cod sursa(job #2099055)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 3 ianuarie 2018 21:33:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <bits/stdc++.h>
#define MAXN 100
#define INF 1000000000

#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a * 10 + c - '0';
        c = nextch();
    }
    return a;
}

int S, D;
std::vector <int> G[1 + 2 + 2 * MAXN];
int C[1 + 2 + 2 * MAXN][1 + 2 + 2 * MAXN];
int F[1 + 2 + 2 * MAXN][1 + 2 + 2 * MAXN];

int q[1 + 2 + 2 * MAXN];
int father[1 + 2 + 2 * MAXN];
int viz[1 + 2 + 2 * MAXN];
int bfs(){
    memset(viz, 0, sizeof(viz));
    q[0] = 1;
    q[1] = S;
    viz[S] = 1;

    for(int i = 1; i <= q[0]; i++){
        int node = q[i];
        if(node != D)
            for(int j = 0; j < G[node].size(); j++){
                int vecin = G[node][j];
                if(!viz[vecin] && C[node][vecin] != F[node][vecin]){
                    viz[vecin] = 1;
                    q[++q[0]] = vecin;
                    father[vecin] = node;
                }
            }
        if(viz[D])
            return viz[D];
    }

    return viz[D];
}

int main(){
    fi = fopen("harta.in","r");
    fo = fopen("harta.out","w");

    int n = nextnum();
    int sum = 0;
    for(int i = 2; i <= n + 1; i++){
        int x = nextnum(), y = nextnum();
        sum += x + y;
        G[1].push_back(i);
        G[i].push_back(1);
        C[1][i] = x;
        G[i + n].push_back(2 * n + 2);
        G[2 * n + 2].push_back(i + n);
        C[i + n][2 * n + 2] = y;
        for(int j = n + 2; j <= 2 * n + 1; j++)
            if(j != i + n){
                G[i].push_back(j);
                G[j].push_back(i);
                C[i][j] = 1;
            }
    }

    S = 1;
    D = 2 * n + 2;

    while(bfs()){
        for(int i = 0; i < G[D].size(); i++){
            int node = G[D][i];
            if(viz[node] && C[node][D] != F[node][D]){
                father[D] = node;

                int fmin = INF;
                for(int node = D; node != S; node = father[node])
                    fmin = std::min(fmin, C[father[node]][node] - F[father[node]][node]);
                if(fmin != 0)
                    for(int node = D; node != S; node = father[node]){
                        F[father[node]][node] += fmin;
                        F[node][father[node]] -= fmin;
                    }
            }
        }
    }

    fprintf(fo,"%d\n", sum / 2);
    for(int i = 2; i <= n + 1; i++)
        for(int j = n + 2; j <= 2 * n + 1; j++)
            if(F[i][j] == C[i][j] && C[i][j])
                fprintf(fo,"%d %d\n", i - 1, j - n - 1);

    fclose(fi);
    fclose(fo);
    return 0;
}