Cod sursa(job #2239224)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 10 septembrie 2018 10:10:05
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");

const int NMAX = 205;

struct Edge {
    int to, cap, flow, rev;
};
vector<Edge> g[NMAX];
int cap[NMAX][NMAX], n, m, rem[NMAX];

void addEdge(int i, int j) {
    Edge a = {j, cap[i][j], 0, g[j].size()};
    Edge b = {i, cap[j][i], 0, g[i].size()};
    g[i].push_back(a);
    g[j].push_back(b);
}

int dist[NMAX];
bool bfs() {
    for(int i = 0; i <= m; i ++)
        dist[i] = -1;

    dist[0] = 0;
    queue<int> q;
    q.push(0);

    while(q.size()) {
        int from = q.front();
        q.pop();
        for(auto it : g[from]) {
            if(dist[it.to] == -1 && it.flow < it.cap) {
                dist[it.to] = 1 + dist[from];
                q.push(it.to);
            }
        }
    }
    return (0 <= dist[m]);
}

int flow[NMAX][NMAX];

int dfs(int from, int deltaflow) {
    if(from == m)
        return deltaflow;
    for(int &i = rem[from]; i < g[from].size(); i ++) {
        Edge &e = g[from][i];
        if(dist[e.to] == 1 + dist[from] && e.flow < e.cap) {
            int addflow = dfs(e.to, min(deltaflow, e.cap - e.flow));
            if(addflow > 0) {
                Edge &rev = g[e.to][e.rev];
                e.flow += addflow;
                rev.flow -= addflow;
                flow[from][e.to] += addflow;
               // cout << from << " " << e.to << " " << flow[from][e.to] << endl;
                flow[e.to][from] -= addflow;
                //cout << from << " " << e.to << " " << flow[e.to][from] << endl;
                return addflow;
            }
        }
    }
    return 0;
}

int dinic() {
    int maxflow = 0;
    while(bfs()) {
        for(int i = 0; i <= m; i ++)
            rem[i] = 0;
        int aux = dfs(0, INT_MAX);
        while(aux) {
            maxflow += aux;
            //cout << maxflow << endl;
            aux = dfs(0, INT_MAX);
        }
    }
    return maxflow;
}

int main() {
    in >> n;
    m = 2 * n + 1;
    for(int i = 1; i <= n; i ++) {
        int x, y;
        in >> x >> y;
        cap[0][i * 2 - 1] = x; /// gradul dr iesire
        addEdge(0, i * 2 - 1);

        cap[i * 2][m] = y; /// gradul de intrare
        addEdge(i * 2, m);
    }

    for(int i = 1; i < m; i += 2)
        for(int j = 2; j < m; j += 2)
            if(j - i != 1)
                cap[i][j] = 1;

    for(int i = 1; i < m; i ++)
        for(int j = i + 1; j < m; j ++)
            if(cap[i][j] || cap[j][i])
                addEdge(i, j);
    int maxflow = dinic();

    vector<pair<int, int> > sol;
    for(int i = 1; i < m; i += 2)
        for(int j = 2; j < m; j += 2)
            if(flow[i][j] == cap[i][j] && j - i != 1)
                sol.push_back({(i + 1) / 2, (j + 1) / 2});

    out << sol.size() << "\n";
    for(auto it : sol)
        out << it.first << " " << it.second << "\n";

    return 0;
}