Pagini recente » Cod sursa (job #849331) | Cod sursa (job #2437814) | template/preoni-2006/finalrankings | Cod sursa (job #551325) | Cod sursa (job #2956112)
#include<bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int root, dest, n, m, d1, d2, c, total, l, r;
int dad[202];
vector<vector<int>>v;
int flux[202][202];
bool viz[202];
bool bfs()
{
queue<int>q;
for (int i = 0; i <= 2*n+1; i++)
{
dad[i] = -1;
viz[i] = 0;
}
viz[0] = 1;
q.push(0);
while (!q.empty())
{
int node = q.front();
q.pop();
for(auto next : v[node])
{
if(viz[next] == 0 && flux[node][next] > 0)
{
dad[next] = node;
q.push(next);
viz[next] = 1;
if(next == 2 * n + 1)
return 1;
}
}
}
return 0;
}
int main()
{
f >> n;
v.resize(2*n + 2);
for (int i = 1; i <= n; i++)
{
f >> d1 >> d2;
flux[0][i] = d1;
flux[n + i][2 * n + 1] = d2;
v[0].push_back(i);
v[i].push_back(0); ///conectam cu sursa
v[n + i].push_back(2 * n + 1);
v[2 * n + 1].push_back(n + i); ///conectam cu terminalul
for (int j = n + 1; j <= 2 * n; j++)
if (j - i != n) /// nu conectam i cu i (nu facem bucle)
{
v[i].push_back(j);
v[j].push_back(i);
flux[i][j] = 1;
}
}
while (bfs())
for (auto next : v[n])
{
if (!viz[next])
continue;
int minim = 2;
int t = 2 * n + 1;
while (t != 0)
{
minim = min(minim, flux[dad[t]][t]);
t = dad[t];
}
t = 2 * n + 1;
while (t != 0)
{
flux[dad[t]][t] -= minim;
flux[t][dad[t]] += minim;
t = dad[t];
}
total = total + minim;
}
g << total << '\n';
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n + 1; j++)
if (flux[j][i] == 1)
{
g << i << ' ' << j - n << '\n';
continue;
}
}