Pagini recente » Cod sursa (job #2299287) | Cod sursa (job #75722) | Cod sursa (job #2245434) | Cod sursa (job #354113) | Cod sursa (job #2334316)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,i,j,dist[210],tata[210],cap[210][210];
priority_queue<pair<int,int> > q;
vector<pair<int,int> > ans;
vector<int> v[210];
bool djikstra()
{
memset(dist,127,sizeof(dist));
memset(tata, 0,sizeof(tata));
q.push({0,0});
dist[0]=0;
while(q.size())
{
int cst=-q.top().first,x=q.top().second;
q.pop();
if(cst>dist[x])continue;
for(auto it:v[x])
if(cap[x][it])
if(dist[it]>dist[x]+1)
{
dist[it]=dist[x]+1;
tata[it]=x;
q.push({-dist[it],it});
}
}
if(dist[2*n+1]>=1e9)return 0;
int flx=1e9;
for(int x=2*n+1;x;x=tata[x])
flx=min(flx,cap[tata[x]][x]);
for(int x=2*n+1;x;x=tata[x])
cap[tata[x]][x]-=flx,cap[x][tata[x]]+=flx;
return 1;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
int a,b;
f>>a>>b;
v[0].push_back(i);
v[i].push_back(0);
cap[0][i]=a;
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
cap[i+n][2*n+1]=b;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
v[i].push_back(j+n);
v[j+n].push_back(i);
cap[i][j+n]=1;
}
// for(i=0;i<=2*n+1;i++)
// {
// g<<i<<": ";
// for(auto it:v[i])
// g<<it<<','<<cap[i][it]<<' ';
// g<<'\n';
// }
for(;djikstra(););
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
if(!cap[i][j+n])
ans.push_back({i,j});
g<<ans.size()<<'\n';
for(auto it:ans)
g<<it.first<<' '<<it.second<<'\n';
return 0;
}