Pagini recente » Monitorul de evaluare | Cod sursa (job #2468126) | Cod sursa (job #2246719) | Cod sursa (job #1393260) | Cod sursa (job #3358914)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int v[101];
int w[101];
int cap[201][201];
int flux[201][201];
vector<int> v1[201];
int tata[201];
bool bfs(int n)
{
vector<bool> aux(201,0);
queue<int> Q;
Q.push(0);
aux[0]=1;
while(!Q.empty())
{
int node=Q.front();
Q.pop();
for(auto it:v1[node])
{
if(aux[it]==0 && cap[node][it]-flux[node][it]>0)
{
aux[it]=1;
tata[it]=node;
Q.push(it);
}
}
}
return aux[2*n+1];
}
void calc_flux(int n)
{
while(bfs(n))
{
int mn=INT_MAX;
for(int i=2*n+1;i>0;i=tata[i])
{
mn=min(mn,cap[tata[i]][i]-flux[tata[i]][i]);
}
for(int i=2*n+1;i>0;i=tata[i])
{
flux[tata[i]][i]+=mn;
flux[i][tata[i]]-=mn;
}
}
}
vector<pair<int,int>> ans;
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i]>>w[i];
v1[0].push_back(i);
v1[i].push_back(0);
cap[0][i]=v[i];
v1[2*n+1].push_back(i+n);
v1[i+n].push_back(2*n+1);
cap[i+n][2*n+1]=w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
v1[i].push_back(j+n);
v1[j+n].push_back(i);
cap[i][j+n]=1;
}
}
}
calc_flux(n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j && cap[i][j+n]-flux[i][j+n]==0)
{
ans.push_back({i,j});
}
}
}
fout<<ans.size()<<'\n';
for(auto it:ans)
{
fout<<it.first<<' '<<it.second<<'\n';
}
return 0;
}