Pagini recente » Cod sursa (job #1060805) | Cod sursa (job #2059002) | Cod sursa (job #1907449) | Cod sursa (job #2194067) | Cod sursa (job #1722121)
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int t[1005] , c[1005][1005] , flow[1005][1005];
int n , m , cost , flux , node1 , node2;
vector <vector <int> > G;
bool bfs();
int main() {
f >> n;
G.resize(2 * n + 5);
int x , y;
for (int i = 1; i <= n; ++i) {
f >> x >> y;
c[1][i + 1] = x;
G[1].push_back(i + 1);
G[i + 1].push_back(1);
c[n + i + 1][2 * n + 2] = y;
G[n + i + 1].push_back(2 * n + 2);
G[2 * n + 2].push_back(n + i + 1);
}
for (int i = 2; i <= n + 1; ++i) {
for (int j = n + 2; j <= 2 * n + 1; ++j) {
if (i - 1 == j - n - 1) {
continue;
}
c[i][j] = 1;
G[i].push_back(j);
G[j].push_back(i);
}
}
while(bfs()) {
for(vector <int>::iterator it = G[2 * n + 2].begin() ; it != G[2 * n + 2].end() ; ++it) {
if(flow[*it][2 * n + 2] < c[*it][2 * n + 2] && t[*it]) {
int u = *it , val = c[*it][2 * n + 2] - flow[*it][2 * n + 2];
while(u != 1) {
val = min(val , c[t[u]][u] - flow[t[u]][u]);
u = t[u];
}
u = *it;
flow[*it][2 * n + 2] += val;
flow[2 * n + 2][*it] -= val;
while(u != 1)
{
flow[t[u]][u] += val;
flow[u][t[u]] -= val;
u = t[u];
}
flux += val;
}
}
}
g << flux << '\n';
for (int i = 2; i <= n + 1; ++i) {
for (int j = n + 2; j <= 2 * n + 1; ++j) {
if (i - 1 == j - n - 1) {
continue;
}
if (flow[i][j] == 1) {
g << i - 1 << " " << j - n - 1 << '\n';
}
}
}
return 0;
}
bool bfs() {
queue <int> q;
q.push(1);
memset(t , 0 , sizeof(t));
t[1] = -1;
while(!q.empty()) {
int node = q.front();
for(vector <int> :: iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
if(flow[node][*it] < c[node][*it] && !t[*it]) {
q.push(*it);
t[*it] = node;
}
}
q.pop();
}
return (t[n] != 0);
}