Pagini recente » Cod sursa (job #262111) | Cod sursa (job #2420447) | Cod sursa (job #3144628) | Cod sursa (job #603954) | Cod sursa (job #1441229)
#include <fstream>
#include <vector>
#include <queue>
#define MAXN 203
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
int n, x, y, source, destination, roads, previous[MAXN], flow[MAXN][MAXN], capacity[MAXN][MAXN];
std::vector<int> graph[MAXN];
std::queue<int> q;
bool accessible()
{
int vertex, neighbour;
unsigned iterator;
for (iterator=1;iterator<=destination;++iterator)
previous[iterator]=-1;
previous[source]=0;
q.push(source);
while (!q.empty())
{
vertex=q.front();
q.pop();
for (iterator=0;iterator<graph[vertex].size();++iterator)
{
neighbour=graph[vertex][iterator];
if (previous[neighbour]==-1 && flow[vertex][neighbour]<capacity[vertex][neighbour])
{
previous[neighbour]=vertex;
q.push(neighbour);
}
}
}
if (previous[destination]==-1)
return false;
return true;
}
void maximum_flow()
{
int vertex, value;
unsigned iterator;
while (accessible())
{
for (iterator=0;iterator<graph[destination].size();++iterator)
{
vertex=graph[destination][iterator];
if (flow[vertex][destination]>=capacity[vertex][destination])
continue;
value=capacity[vertex][destination]-flow[vertex][destination];
while (previous[vertex])
{
value=std::min(value, capacity[previous[vertex]][vertex]-flow[previous[vertex]][vertex]);
vertex=previous[vertex];
}
roads+=value;
vertex=graph[destination][iterator];
flow[vertex][destination]+=value;
flow[destination][vertex]-=value;
while (previous[vertex])
{
flow[previous[vertex]][vertex]+=value;
flow[vertex][previous[vertex]]-=value;
vertex=previous[vertex];
}
}
}
}
int main()
{
unsigned i, j;
//std::ios_base::sync_with_stdio(false);
fin>>n;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
if(i == j)
continue;
graph[i].push_back(j+n);
graph[j+n].push_back(i);
capacity[i][j+n]=1;
}
source=2*n+1;
destination=2*n+2;
for(i = 1; i <= n; ++i)
{
fin>>x>>y;
graph[source].push_back(i);
graph[i].push_back(source);
capacity[source][i]=x;
graph[i+n].push_back(destination);
graph[destination].push_back(i+n);
capacity[i+n][destination]=y;
}
maximum_flow();
fout<<roads<<'\n';
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
if (i==j)
continue;
if (flow[i][j+n])
fout<<i<<' '<<j<<'\n';
}
return 0;
}