Pagini recente » Borderou de evaluare (job #2247991) | Cod sursa (job #3207996) | Cod sursa (job #2165947) | Cod sursa (job #2598530) | Cod sursa (job #2951505)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int NMAX = 202;
int n, in[NMAX], out[NMAX], RG[NMAX][NMAX];
vector<int> G[NMAX];
void read(){
f >> n;
for(int i = 1; i <= n; ++i){
f >> out[i] >> in[i];
}
}
bool BFS(int s, int t, vector<int>& parent){
fill(parent.begin(), parent.end(), -1);
vector<bool> visited(NMAX, false);
queue<int> Q;
Q.push(s);
visited[s] = true;
parent[s] = -1;
while(!Q.empty()){
int node = Q.front();
Q.pop();
for(auto i : G[node]){
if(!visited[i] && RG[node][i]){
if(i == t){
parent[i] = node;
return true;
}
Q.push(i);
parent[i] = node;
visited[i] = true;
}
}
}
return false;
}
void solve(){
int max_flow = 0, s = 0, t = 2 * n + 1;
vector<int> parent(NMAX, -1);
for(int i = 1; i <= n; ++i){
RG[s][i] = in[i];
G[s].push_back(i);
G[i].push_back(s);
RG[n + i][t] = out[i];
G[n + i].push_back(t);
G[t].push_back(n + i);
}
for(int i = 1; i <= n; ++i)
for(int j = n + 1; j <= 2 * n; ++j)
if(n + i != j){
RG[i][j] = RG[j][i] = 1;
G[i].push_back(j);
G[j].push_back(i);
}
while(BFS(s, t, parent)){
int path_flow = INT_MAX;
// find the max flow through the path
for(int node = t; node != s; node = parent[node]){
int aux = parent[node];
path_flow = min(path_flow, RG[aux][node]);
}
// update
for(int node = t; node != s; node = parent[node]){
int aux = parent[node];
RG[aux][node] -= path_flow;
RG[node][aux] += path_flow;
}
max_flow += path_flow;
}
g << max_flow << '\n';
for(int i = 1; i <= n; ++i){
for(int j = n + 1; j <= 2 * n; ++j)
if(n + i != j && RG[i][j] == 0)
g << i << ' ' << j - n << '\n';
}
}
int main(){
read();
solve();
return 0;
}