Pagini recente » Monitorul de evaluare | Cod sursa (job #2279138) | Cod sursa (job #1892230) | Cod sursa (job #219780) | Cod sursa (job #1774168)
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int nmax=205;
vector<int> v[nmax];
int prec[nmax],q[nmax],fl[nmax][nmax],c[nmax][nmax];
int p,u,n,i,j,start,source,sink,sum,node;
bool ok;
bool bfs()
{
for(i=1;i<=2*n+1;i++)
prec[i]=0;
prec[source]=-1;
p=1;u=1;q[p]=source;
while(p<=u)
{
start=q[p];p++;
if(start==sink) return 1;
for(j=0;j<v[start].size();j++)
{
i=v[start][j];
if(prec[i]==0)
{
if(fl[start][i]<c[start][i])
{
prec[i]=start;
u++;q[u]=i;
}
else
{
if(fl[i][start]>0)
{
prec[i]=-start;
u++;q[u]=i;
}
}
}
}
}
return 0;
}
int main()
{
ifstream f("harta.in");
ofstream g("harta.out");
f>>n;
source=2*n+2;sink=2*n+1;
for(i=1;i<=n;i++)
{
f>>c[source][i]>>c[n+i][sink];
sum+=c[source][i];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
c[i][n+j]=1;
v[i].push_back(n+j);
v[n+j].push_back(i);
}
for(i=1;i<=n;i++)
{
v[source].push_back(i);
v[i].push_back(source);
v[n+i].push_back(sink);
}
ok=1;
while(ok)
{
ok=bfs();
if(ok==0) continue;
node=sink;
while(node!=source)
{
if(prec[node]>=0)
{
fl[prec[node]][node]++;
}
else
{
fl[node][-prec[node]]--;
}
node=prec[node];
if(node<0) node*=-1;
}
}
g<<sum<<'\n';
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(fl[i][j]>0)
g<<i<<' '<<j-n<<'\n';
return 0;
}