Pagini recente » Cod sursa (job #1671673) | Cod sursa (job #3235942) | Cod sursa (job #3031991) | Cod sursa (job #578272) | Cod sursa (job #3263423)
#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;
}