Pagini recente » Cod sursa (job #47937) | Cod sursa (job #977273) | Cod sursa (job #1917292) | Cod sursa (job #1064519) | Cod sursa (job #2691262)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,cap[205][205],flux[205][205],tata[205],nr;
bool fost[205];
vector<int>vecini[205];
queue<int>coada;
bool pompeaza()
{
for(int i=0; i<=n+n+1; i++) fost[i]=0;
coada.push(0);
fost[0]=1;
while(!coada.empty())
{
int nod=coada.front();
coada.pop();
if(nod==2*n+1) continue;
for(int i=0; i<vecini[nod].size(); i++)
{
int x=vecini[nod][i];
if(fost[x]||cap[nod][x]==flux[nod][x]) continue;
coada.push(x);
fost[x]=1;
tata[x]=nod;
}
}
return fost[2*n+1];
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
{
int a,b;
f>>a>>b;
nr+=a;
cap[0][i]=a;
vecini[i].push_back(0);
vecini[0].push_back(i);
for(int j=1; j<=n; j++)
if(i!=j) vecini[i].push_back(j+n),vecini[j+n].push_back(i),cap[i][j+n]=1;
cap[i+n][2*n+1]=b;
vecini[i+n].push_back(2*n+1);
vecini[2*n+1].push_back(i+n);
}
g<<nr<<'\n';
while( pompeaza() )
{
for(int i=0; i<vecini[2*n+1].size(); i++)
{
int x=vecini[2*n+1][i];
if( !fost[x]&&cap[2*n+1][x]==flux[2*n+1][x] ) continue;
tata[2*n+1]=x;
int cup=100005;
for(int j=2*n+1; j!=0; j=tata[j]) cup=min(cup,cap[tata[j]][j]-flux[tata[j]][j]);
if(cup==0) continue;
for(int j=2*n+1; j!=0; j=tata[j]){
flux[tata[j]][j]+=cup;
flux[j][tata[j]]-=cup;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(flux[i][j+n]!=0) g<<i<<' '<<j<<'\n';
}