Pagini recente » Cod sursa (job #355804) | Cod sursa (job #793934) | Cod sursa (job #2253045) | Cod sursa (job #1955898) | Cod sursa (job #2680112)
#include <bits/stdc++.h>
using namespace std;
ifstream r("harta.in");
ofstream w("harta.out");
int n, parent[203], rez[203][203];
bool viz[203];
vector<int>g[203];
bool bfs()
{
memset(viz, 0, sizeof(viz));
queue<int>q;
q.push(0);
viz[0]=1;
parent[0]=-1;
while(q.size()!=0)
{
int a=q.front();
q.pop();
if(a!=2*n+1)
{
for(auto it: g[a])
{
if(viz[it]==0 && rez[a][it]>0)
{
q.push(it);
parent[it]=a;
viz[it]=true;
}
}
}
}
return viz[2*n+1];
}
int flux()
{
int flow=0;
while(bfs()!=0)
{
for(auto it: g[2*n+1])
{
if(rez[it][2*n+1]>0 && viz[it]==1)
{
parent[2*n+1]=it;
int fluxm=1000000000, nod=2*n+1;
while(nod!=0)
{
fluxm=min(fluxm, rez[parent[nod]][nod]);
nod=parent[nod];
}
nod=n*2+1;
while(nod!=0)
{
rez[parent[nod]][nod]-=fluxm;
rez[nod][parent[nod]]+=fluxm;
nod=parent[nod];
}
flow+=fluxm;
}
}
}
return flow;
}
int main()
{
r>>n;
for(int i=1;i<=n;i++){
int x, y;
r>>x>>y;
g[0].push_back(i);
g[i].push_back(0);
rez[0][i]=x;
g[i+n].push_back(2*n+1);
g[2*n+1].push_back(i+n);
rez[i+n][2*n+1]=y;
}
for(int i=1;i<=n;i++){
for(int j=n+1;j<=2*n;j++){
if(i+n!=j){
g[i].push_back(j);
g[j].push_back(i);
rez[i][j]=1;
}
}
}
w<<flux()<<"\n";
for(int i=1;i<=n;i++){
for(int j=n+1;j<=2*n;j++){
if(i+n!=j && rez[i][j]==0){
w<<i<<" "<<j-n<<"\n";
}
}
}
return 0;
}