Cod sursa(job #3263423)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 14 decembrie 2024 12:06:26
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

int const INF = 1e9+7;

struct Edge{
  int from;
  int to;
  int flow;
};

int const NMAX = 200;
vector <Edge> edges;  
int dist[1 + NMAX];
vector <int> g[1 + NMAX];
int edge_ind[1 + NMAX];

void addEdge(int from, int to, int flow) {
  edges.push_back({from, to, flow});
  edges.push_back({to, from, 0});
  g[from].push_back(edges.size()-2);
  g[to].push_back(edges.size()-1);
}

void buildNetwork(int n) {
  for(int i = 1;i <= n;i++) { 
    int a, b;
    in >> a >> b;
    addEdge(0, i, a);
    addEdge(n + i, 2 * n + 1, b);
  }
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      if(i != j) {
        addEdge(i, n + j, 1);   
      }
    }
  }
}

void BFS(int source, int n) {
  for(int i = 0;i <= n;i++) {
    dist[i] = INF;
    edge_ind[i] = 0;
  }
  queue <int> q;
  q.push(source);
  dist[source] = 0;
  while(!q.empty()) {
    int from = q.front();
    q.pop();
    for(int i = 0;i < g[from].size();i++) {
      int to = edges[g[from][i]].to, flow = edges[g[from][i]].flow;
      if(flow > 0 && dist[from] + 1 < dist[to]) {
	dist[to] = dist[from] + 1;
        q.push(to);	
      }
    }
  }
}

int doPush(int node, int minflow, int sink) {
  if(node == sink) {
    return minflow; 
  }else { 
    int pushed = 0;
    for(int &i = edge_ind[node];i < g[node].size();i++) {
      int to = edges[g[node][i]].to, flow = edges[g[node][i]].flow;
      if(flow > 0 && dist[node] < dist[to]) {
        int temp = doPush(to, min(minflow - pushed, flow), sink);	
	if(pushed + temp <= minflow) {
	  pushed += temp;
	  edges[g[node][i]].flow -= temp;
	  edges[g[node][i] ^ 1].flow += temp;
        }
      }
      if(minflow - pushed == 0) {
	return pushed;
      }
    }
    return pushed;
  }
}

void computeDinic(int source, int sink, int n) {
  bool finish = false;
  while(!finish) {
    BFS(source, n); 
    int temp = doPush(source, sink, n);  
    if(temp == 0) { 
      finish = true;
    }
  }
}

void buildGraph(int n) {
  vector <pair <int, int>> ans;
  for(int k = 0;k < edges.size();k += 2) {
    int from = edges[k].from, to = edges[k].to, flow = edges[k].flow;
    if(flow == 0 && (1 <= from && from <= n) && (n + 1 <= to && to <= 2 * n)) {
      ans.push_back({from, to - n});
    }
  }
  out << ans.size() << '\n';
  for(int i = 0;i < ans.size();i++) {
    out << ans[i].first << ' ' << ans[i].second << '\n';
  }
}

int main() {

  int n;
  in >> n;
  buildNetwork(n); 
  computeDinic(0, 2 * n + 1, 2 * n + 1);
  buildGraph(n); 
  return 0;
}