Pagini recente » Cod sursa (job #197654) | Cod sursa (job #1809475) | Cod sursa (job #1194986) | Cod sursa (job #1944286) | Cod sursa (job #754309)
Cod sursa(job #754309)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
#define N 230
#define inf 10000000
int n, c[N][N], f[N][N], p[N], s, d;
vector<int> v[N];
bool bf() {
queue<int> q;
int i, el;
for(i = s; i<=d; ++i)
p[i] = -1;
q.push(s);
p[s] = 0;
while(!q.empty()) {
el = q.front();
q.pop();
if(el!=d)
for(vector<int>::iterator it = v[el].begin(); it!=v[el].end(); ++it)
if(p[*it] == -1 && c[el][*it] > f[el][*it]) {
p[*it] = el;
q.push(*it);
}
}
return p[d]!=-1;
}
void flux() {
int j, smin;
vector<int>::iterator it;
while(bf())
for(it = v[d].begin(); it!=v[d].end(); ++it)
if(c[*it][d] > f[*it][d]) {
smin = c[*it][d] - f[*it][d];
for(j = *it; j!=s; j = p[j])
if(c[p[j]][j] - f[p[j]][j] < smin)
smin = c[p[j]][j] - f[p[j]][j];
f[*it][d] += smin;
f[d][*it] -= smin;
for(j = *it; j!=s; j = p[j]) {
f[p[j]][j] += smin;
f[j][p[j]] -= smin;
}
}
}
int main() {
int i, j, x, y, ss = 0;
in >> n;
s = 1; d = 2 * (n + 1);
for(i = 1; i<=n; ++i) {
in >> x >> y;
ss+=y;
c[s][i + 1] = x;
c[i + n + 1][d] = y;
v[s].push_back(i + 1);
v[i + 1].push_back(s);
v[i + n + 1].push_back(d);
v[d].push_back(i + n + 1);
for(j = 1; j<=n; ++j) if(j!=i) {
c[j + 1][i + n + 1] = 1;
v[j + 1].push_back(i + n + 1);
v[i + n + 1].push_back(j + 1);
}
}
flux();
out << ss << "\n";
for(i = 1; i<=d/2; ++i)
for(j = 1; j<=d/2; ++j) if(i!=j && f[i + 1][j + n + 1])
out << i << " " << j << "\n";
return 0;
}