Pagini recente » Cod sursa (job #1104254) | Cod sursa (job #1316633) | Cod sursa (job #1565234) | Cod sursa (job #2143141) | Cod sursa (job #987707)
Cod sursa(job #987707)
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 102;
const int INF = 0x3f3f3f3f;
int N, sol;
int Flow[MAX_N*2][MAX_N*2], Capacity[MAX_N*2][MAX_N*2], F[MAX_N*2];
vector < int > v[MAX_N*2];
vector < pair < int, int > > a;
queue < int > Q;
inline bool BFS(int S, int D) {
memset(F, 0, sizeof(F));
F[S] = S;
Q.push(S);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
if(x == D)
continue;
for(size_t i = 0; i < v[x].size(); ++i) {
int y = v[x][i];
if(F[y] || Flow[x][y] >= Capacity[x][y])
continue;
F[y] = x, Q.push(y);
}
}
return (F[D] != 0);
}
int main() {
ifstream f("harta.in");
ofstream g("harta.out");
f >> N;
int S = 2*N+1, D = 2*N+2;
for(int i = 1, x, y; i <= N; ++i) {
f >> x >> y;
v[S].push_back(i), v[i].push_back(S), Capacity[S][i] += x;
v[N+i].push_back(D), v[D].push_back(N+i), Capacity[N+i][D] += y;
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(i != j)
v[i].push_back(N+j), v[N+j].push_back(i), Capacity[i][N+j] += 1;
int sum = 0;
while(BFS(S, D)) {
for(size_t i = 0; i < v[D].size(); ++i) {
int y = v[D][i];
if(!F[y] || Flow[y][D] >= Capacity[y][D])
continue;
F[D] = y;
int MinFlow = INF;
for(int x = D; x != S; x = F[x])
MinFlow = min(MinFlow, Capacity[F[x]][x] - Flow[F[x]][x]);
for(int x = D; x != S; x = F[x])
Flow[F[x]][x] += MinFlow, Flow[x][F[x]] = -Flow[F[x]][x];
sum += MinFlow;
}
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(Flow[i][N+j])
++sol, a.push_back(make_pair(i, j));
g << sol << "\n";
for(size_t i = 0; i < a.size(); ++i)
g << a[i].first << " " << a[i].second << "\n";
f.close();
g.close();
return 0;
}