Pagini recente » Cod sursa (job #617803) | Cod sursa (job #3155660) | Cod sursa (job #3194250) | Borderou de evaluare (job #202912) | Cod sursa (job #1223383)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 100, NR = 2 * N + 1;
class Queue{
int v[NR], st, dr;
public:
void reset(){
st = dr = 0;
}
inline void push(int x){
v[st++] = x;
}
inline int pop(){
return v[dr++];
}
inline bool isEmpty(){
return st == dr;
}
};
int cf[NR][NR], T[NR], n;
Queue Q;
inline void relax(int x, int y, int F){
cf[x][y] -= F;
cf[y][x] += F;
}
bool bfs(int x, int D){
memset(T, -1, sizeof(T));
Q.reset();
Q.push(x);
while (!Q.isEmpty()){
x = Q.pop();
for (int y = 1 ; y <= D ; y++)
if ( T[y] == -1 && cf[x][y] ){
Q.push(y);
T[y] = x;
}
}
return T[D] != -1;
}
int maxFlow(int S, int D){
int flow = 0;
while ( bfs(S, D) )
for (int x = n + 1 ; x <= 2 * n ; x++){
int F = cf[x][D];
if (!F) continue;
for (int i = x ; i != S ; i = T[i])
F = min(F, cf[ T[i] ][i]);
if (!F) continue;
relax(x, D, F);
for (int i = x ; i != S ; i = T[i])
relax(T[i], i, F);
flow += F;
}
return flow;
}
int main(){
ifstream in("harta.in");
in >> n;
int S = 0, D = 2 * n + 1;
for (int i = 1 ; i <= n ; i++)
in >> cf[S][i] >> cf[i + n][D];
in.close();
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= n ; j++)
cf[i][j + n] = (i != j);
ofstream out("harta.out");
out << maxFlow(S, D) << '\n';
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= n ; j++)
if ( i != j && !cf[i][j + n] )
out << i << ' ' << j << '\n';
out.close();
return 0;
}