Pagini recente » Cod sursa (job #1390385) | Cod sursa (job #3306580) | Cod sursa (job #604586) | Cod sursa (job #2966941) | Cod sursa (job #3320965)
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
const string txt = "data", file = "harta";
const int nmax = 1e5 + 5;
ifstream f(file + ".in");
ofstream g(file + ".out");
int n, flow[205][205], t[205], viz[205];
vector<int> v[205];
vector<pair<int, int>> ans;
bool bfs()
{
queue<int> q; while (!q.empty()) q.pop();
q.push(0); fill(viz, viz + 201, 0);
fill(t, t + 201, 0); viz[0] = 1;
while (!q.empty())
{
int node = q.front(); q.pop();
for (auto x : v[node]) {
if (viz[x] || flow[node][x] <= 0) continue;
viz[x] = 1; t[x] = node; q.push(x);
}
}
return viz[2 * n + 1];
}
void maxflow()
{
int i = 1;
while(bfs())
{
int sum = 1000;
for (int i = 2 * n + 1; i != 0; i = t[i])
sum = min(sum, flow[t[i]][i]);
for (int i = 2 * n + 1; i != 0; i = t[i])
flow[t[i]][i] -= sum, flow[i][t[i]] += sum;
}
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> flow[0][i] >> flow[i + n][2 * n + 1];
v[0].push_back(i); v[i].push_back(0);
v[2 * n + 1].push_back(i + n);
v[i + n].push_back(2 * n + 1);
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j++)
if (i != j) {
v[i].push_back(j + n);
v[j + n].push_back(i);
flow[i][j + n] = 1;
}
maxflow();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && !flow[i][j + n])
ans.push_back({ i, j });
g << ans.size() << '\n';
for (auto x : ans)
g << x.first << " " << x.second << '\n';
return 0;
}