Cod sursa(job #1463043)

Utilizator jul123Iulia Duta jul123 Data 19 iulie 2015 19:07:21
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include<bits/stdc++.h>

using namespace std;

vector<int>v[300];
vector<pair<int, int> >ans;
queue<int>q;
int tata[300], viz[300], f[300][300], c[300][300];
int n;

int bfs() {
    for(int i = 0; i <= 2 * n + 1; ++i)
        viz[i] = 0;
    q.push(0);
    viz[0] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        if(x != 2 * n + 1)
        for(int i = 0; i < v[x].size(); ++i) {
            int nod = v[x][i];
            if(viz[nod] == 0 && f[x][nod] != c[x][nod]) {
                viz[nod] = 1;
                q.push(nod);
                tata[nod] = x;
            }
        }
    }
    return viz[2 * n + 1];

}

int main()
{
    int in, out;
    FILE *fin = fopen("harta.in", "r");
    FILE *fout = fopen("harta.out", "w");

    fscanf(fin, "%d", &n);

    for(int i = 1; i <= n; ++i) {
        fscanf(fin, "%d %d", &in, &out);
        v[0].push_back(i);
        v[i].push_back(0);
        c[0][i] = in;
        v[n + i].push_back(2 * n + 1);
        v[2 * n + 1].push_back(n + i);
        c[n + i][2 * n + 1] = out;
    }

    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){
            v[i].push_back(n + j);
            v[n + j].push_back(i);
            v[j].push_back(n + i);
            v[n + i].push_back(j);
            c[i][n + j] = 1;
            c[j][n + i] = 1;
        }

    int flow = 0;
    while(bfs()) {
        for(int i = 0; i < v[2 * n + 1].size(); ++i) {
            int nod = v[2 * n + 1][i];
            if(viz[nod] == 1 && f[nod][2 * n + 1] != c[nod][2 * n + 1]) {
                tata[2 * n + 1] = nod;
                int minim = 1000000000;
                for(int j = 2 * n + 1; j != 0; j = tata[j])
                    if(minim > c[tata[j]][j] - f[tata[j]][j] )
                        minim = c[tata[j]][j] - f[tata[j]][j];
                if(minim != 0) {
                    for(int j = 2 * n + 1; j != 0; j = tata[j]) {
                        f[tata[j]][j] += minim;
                        f[j][tata[j]] -= minim;
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = n + 1; j <= 2 * n; ++j) {
            if(n + i != j) {
                if(f[i][j] == c[i][j])
                    ans.push_back(make_pair(i, j - n));
            }
    }

    fprintf(fout, "%d\n", ans.size());

    for(int i = 0; i < ans.size(); ++i) {
        fprintf(fout, "%d %d\n", ans[i].first, ans[i].second);
    }




}