Pagini recente » Cod sursa (job #821578) | Cod sursa (job #2082359) | Cod sursa (job #2635803) | Cod sursa (job #1304606) | Cod sursa (job #2962282)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, m, e, mxflow;
int viz[205];
int tata[205];
int flux[205][205], c[205][205];
vector <int> adjlist[205];
int grin[205],grout[205];
bool modifiedBfs(int finish)
{
for(int i = 0; i <= 2*n+1; i++)
viz[i]=0,tata[i]=0;
int nod=0;
queue <int> Q;
Q.push(nod);
viz[nod] = 1;
tata[0] = -1;
while(!Q.empty())
{
nod = Q.front();
Q.pop();
for(int i=0; i<adjlist[nod].size(); i++)
{
int vecin=adjlist[nod][i];
if(viz[vecin]!=1 && c[nod][vecin] - flux[nod][vecin] > 0)
{
viz[vecin] = 1;
tata[vecin] = nod;
Q.push(vecin);
}
}
}
if(!tata[finish])
return false;
int start=0;
for(int i=0; i<adjlist[finish].size(); i++)
{
int vecin=adjlist[finish][i];
if(c[vecin][finish] - flux[vecin][finish] > 0)
{
int maxFlowLant = c[vecin][finish] - flux[vecin][finish];
for(int j = vecin; j != start; j = tata[j])
{
maxFlowLant = min(maxFlowLant, c[tata[j]][j] - flux[tata[j]][j]);
}
flux[vecin][finish] += maxFlowLant;
flux[finish][vecin] -= maxFlowLant;
for(int j = vecin; j != start; j = tata[j])
{
flux[tata[j]][j] += maxFlowLant;
flux[j][tata[j]] -= maxFlowLant;
}
mxflow += maxFlowLant;
}
}
return true;
}
int main()
{
f>>n;
int start=0, finish=n*2+1;
int x, y;
for(int i = 1; i <= n; i++)
{
f>>x>>y;
grout[i]=x;
grin[i]=y;
c[start][i]=x;
adjlist[start].push_back(i);
adjlist[i].push_back(start);
c[i+n][finish]=y;
adjlist[finish].push_back(i+n);
adjlist[i+n].push_back(finish);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i!=j)
{
adjlist[i].push_back(j+n);
adjlist[j+n].push_back(i);
c[i][j+n]=1;
}
while(modifiedBfs(finish)==true)
{
modifiedBfs(finish);
}
g<<mxflow<<endl;
for(int i = 1; i <= n; i++)
{
for(int j = n+1; j <= 2*n; j++)
{
if(flux[i][j] == c[i][j] && flux[i][j] == 1)
{
g<<i<< " "<<j - n<< "\n";
}
}
}
return 0;
}