Pagini recente » Cod sursa (job #3288360) | Cod sursa (job #2127869) | Cod sursa (job #791484) | Cod sursa (job #1549339) | Cod sursa (job #1998329)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 2 * 100 + 20;
const int INF = 1 << 30;
const int DIM = 10000;
int n, m, src, dest;
int nin[1 + NMAX], nout[1 + NMAX];
int cap[1 + NMAX][1 + NMAX];
bool vis[1 + NMAX];
int p[1 + NMAX];
int a[1 + NMAX][1 + NMAX];
char buff[DIM];
int poz;
vector < int > g[1 + NMAX];
int read(){
int x = 0;
while(!isdigit(buff[poz]))
if(++poz == DIM){
in.read(buff,DIM);
poz = 0;
}
while(isdigit(buff[poz])){
x = x * 10 + (buff[poz] - '0');
if(++poz == DIM){
in.read(buff,DIM);
poz = 0;
}
}
return x;
}
void addedge(int i, int j, int fl){
cap[i][j] = fl;
g[i].push_back(j);
g[j].push_back(i);
}
int trans(int x){
if(n < x)
return x - n;
else
return x + n;
}
bool bfs(){
fill(vis, vis + NMAX, 0);
fill(p, p + NMAX, 0);
queue < int > q;
q.push(src);
while(!q.empty()){
int from = q.front();
q.pop();
for(int i = 0; i < g[from].size(); i++){
int to = g[from][i];
if(vis[to] == false && cap[from][to] - a[from][to] > 0){
q.push(to);
vis[to] = 1;
p[to] = from;
}
}
}
return vis[dest];
}
void updateg(){
for(int i = 1; i <= n; i++){
addedge(src, i, nout[i]);
addedge(trans(i), dest, nin[i]);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j){
addedge(i, trans(j), 1);
addedge(j, trans(i), 1);
}
}
}
}
int solve(){
int minn = INF;
for(int i = dest; i != src; i = p[i])
minn = min(minn, cap[p[i]][i] - a[p[i]][i]);
for(int i = dest; i != src; i = p[i]){
a[p[i]][i] += minn;
a[i][p[i]] -= minn;
}
return minn;
}
void maxflow(){
int answer = 0;
while(bfs())
answer += solve();
out << answer << '\n';
for(int i = 1; i <= n * 2; i++){
for(int j = 1; j <= n * 2; j++){
if(a[i][j] > 0){
out << ((i > n) ? (i - n) : i) << ' ';
out << ((j > n) ? (j - n) : j) << '\n';
}
}
}
}
void getdata(){
n = read();
src = 0;
dest = n * 2 + 1;
for(int i = 1; i <= n; i++){
nout[i] = read();
nin[i] = read();
}
}
int main()
{
getdata();
updateg();
maxflow();
return 0;
}