Pagini recente » Diferente pentru problema/algoritm intre reviziile 80 si 20 | Borderou de evaluare (job #1625981) | Rezultatele filtrării | Cod sursa (job #2739356) | Cod sursa (job #1463043)
#include<bits/stdc++.h>
using namespace std;
vector<int>v[300];
vector<pair<int, int> >ans;
queue<int>q;
int tata[300], viz[300], f[300][300], c[300][300];
int n;
int bfs() {
for(int i = 0; i <= 2 * n + 1; ++i)
viz[i] = 0;
q.push(0);
viz[0] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
if(x != 2 * n + 1)
for(int i = 0; i < v[x].size(); ++i) {
int nod = v[x][i];
if(viz[nod] == 0 && f[x][nod] != c[x][nod]) {
viz[nod] = 1;
q.push(nod);
tata[nod] = x;
}
}
}
return viz[2 * n + 1];
}
int main()
{
int in, out;
FILE *fin = fopen("harta.in", "r");
FILE *fout = fopen("harta.out", "w");
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i) {
fscanf(fin, "%d %d", &in, &out);
v[0].push_back(i);
v[i].push_back(0);
c[0][i] = in;
v[n + i].push_back(2 * n + 1);
v[2 * n + 1].push_back(n + i);
c[n + i][2 * n + 1] = out;
}
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j){
v[i].push_back(n + j);
v[n + j].push_back(i);
v[j].push_back(n + i);
v[n + i].push_back(j);
c[i][n + j] = 1;
c[j][n + i] = 1;
}
int flow = 0;
while(bfs()) {
for(int i = 0; i < v[2 * n + 1].size(); ++i) {
int nod = v[2 * n + 1][i];
if(viz[nod] == 1 && f[nod][2 * n + 1] != c[nod][2 * n + 1]) {
tata[2 * n + 1] = nod;
int minim = 1000000000;
for(int j = 2 * n + 1; j != 0; j = tata[j])
if(minim > c[tata[j]][j] - f[tata[j]][j] )
minim = c[tata[j]][j] - f[tata[j]][j];
if(minim != 0) {
for(int j = 2 * n + 1; j != 0; j = tata[j]) {
f[tata[j]][j] += minim;
f[j][tata[j]] -= minim;
}
}
}
}
}
for(int i = 1; i <= n; ++i)
for(int j = n + 1; j <= 2 * n; ++j) {
if(n + i != j) {
if(f[i][j] == c[i][j])
ans.push_back(make_pair(i, j - n));
}
}
fprintf(fout, "%d\n", ans.size());
for(int i = 0; i < ans.size(); ++i) {
fprintf(fout, "%d %d\n", ans[i].first, ans[i].second);
}
}