Pagini recente » Cod sursa (job #2081397) | Cod sursa (job #2876761) | Cod sursa (job #1953138) | Cod sursa (job #1959955) | Cod sursa (job #3190126)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
int n;
int graph[102][102], usedCap[102][102];
vector<int> augPath_rev;
int augumentation;
bool findAugPath()
{
augPath_rev.clear();
augumentation=INT_MAX;
vector<int> dads(2*n+2, -1);
queue<int> curLvl;
queue<int> nextLvl;
curLvl.push(0);
bool found=false;
while(!curLvl.empty())
{
while(!curLvl.empty())
{
int x=curLvl.front();
curLvl.pop();
if(x==0)
{
for(int i=1;i<=n;i++)
if(usedCap[x][i]<graph[x][i] && dads[i]==-1)
{
dads[i]=x;
augumentation=min(augumentation, graph[x][i]-usedCap[x][i]);
nextLvl.push(i);
}
}
else if(x<=n)
{
for(int i=n+1;i<=2*n;i++)
if(usedCap[x][i-n]<graph[x][i-n] && dads[i]==-1)
{
dads[i]=x;
augumentation=min(augumentation, graph[x][i-n]-usedCap[x][i-n]);
nextLvl.push(i);
}
}
else if(x<=2*n)
{
if(graph[x-n][n+1]>usedCap[x-n][n+1])
{
dads[2*n+1]=x;
augumentation=min(augumentation, graph[x-n][n+1]-usedCap[x-n][n+1]);
curLvl=queue<int>();
nextLvl=queue<int>();
found=true;
}
else
{
for(int i=1;i<=n;i++)
if(usedCap[i][x-n]>0 && dads[i]==-1)
{
dads[i]=x;
augumentation=min(augumentation, usedCap[i][x-n]);
nextLvl.push(i);
}
}
}
}
curLvl=nextLvl;
nextLvl=queue<int>();
}
if(!found)
{
augumentation=0;
return false;
}
int x=2*n+1;
while(x!=-1) {
augPath_rev.push_back(x);
x = dads[x];
}
return true;
}
void augumentPath()
{
int src, dst;
src=augPath_rev[augPath_rev.size()-1];
augPath_rev.pop_back();
while(!augPath_rev.empty())
{
dst=augPath_rev[augPath_rev.size()-1];
if(src==0)
usedCap[src][dst]+=augumentation;
else if(src<=n)
usedCap[src][dst-n]+=augumentation;
else if(dst==2*n+1)
usedCap[src-n][dst-n]+=augumentation;
else
usedCap[src-n][dst]-=augumentation;
src=dst;
augPath_rev.pop_back();
}
}
int main() {
in>>n;
int totalCap=0;
for(int i=1;i<=n;i++)
{
in>>graph[0][i]>>graph[i][n+1];
totalCap+=graph[0][i];
for(int j=1;j<=n;j++)
graph[i][j]=1;
graph[i][i]=0;
}
while(findAugPath())
augumentPath();
/*int totalCap=0;
for(int i=1;i<=n;i++) {
//if (graph[0][i] == usedCap[0][i])
totalCap+=usedCap[0][i];
//else {
// out << 0;
//return 0;
//}
}*/
out<<totalCap<<'\n';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(usedCap[i][j])
out<<i<<' '<<j<<'\n';
return 0;
}