Pagini recente » Cod sursa (job #3361116) | Cod sursa (job #3359505) | Cod sursa (job #3359509) | Cod sursa (job #3361532) | Cod sursa (job #3363784)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> v[1009];
bool viz[1009];
queue <int> q;
int N;
int ans[10009];
int tata[1009], r[1009][1009], s, d, sol=0, n;
bool bfs ()
{
for (int i=1; i<=N; i++)
viz[i]=0, tata[i]=0;
q.push(s);
viz[s]=1;
while (!q.empty())
{
int x=q.front();
q.pop();
for (auto y:v[x])
{
if (!viz[y] && r[x][y]>0)
{
viz[y]=1;
tata[y]=x;
q.push(y);
}
}
}
return viz[d];
}
void flux_maxim ()
{
int flow=0;
while (bfs())
{
for (auto y:v[d])
{
if ((tata[y]!=0 || y==s) && r[y][d]>0)
{
flow=r[y][d];
for (int j=y; j!=s; j=tata[j])
{
flow=min (flow, r[tata[j]][j]);
if (!flow)
break;
}
if (flow)
{
r[y][d]-=flow;
r[d][y]+=flow;
for (int j=y; j!=s; j=tata[j])
{
r[tata[j]][j]-=flow;
r[j][tata[j]]+=flow;
}
sol+=flow;
}
}
}
}
}
signed main ()
{
int m;
f >> n;
s=2*n+1, d=2*n+2, N=2*n+2;
for (int j=1; j<=n; j++)
{
int a, b;
f >> a >> b;
v[s].push_back(j);
v[j].push_back(s);
r[s][j]+=a;
v[d].push_back(j+n);
v[j+n].push_back(d);
r[j+n][d]+=b;
}
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);
r[i][j+n]=1;
r[j+n][i]=0;
}
}
}
flux_maxim();
vector <pair <int, int> > ans;
g << sol<<'\n';
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (i!=j && r[i][j+n]==0)
ans.push_back ({i, j});
}
}
for (auto p:ans)
{
g << p.first << ' ' << p.second<<'\n';
}
}