Pagini recente » Cod sursa (job #2321457) | Cod sursa (job #1447382) | Cod sursa (job #2872351) | Cod sursa (job #2651443) | Cod sursa (job #2957306)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int capacity[205][205],n,m,flow,max_flow;
vector<int> visited,parent;
bool bfs()
{
fill(visited.begin(), visited.end(), 0);
fill(parent.begin(), parent.end(), 0);
visited[0] = 1;
parent[0] = -1;
queue<int> q;
q.push(0);
while(!q.empty())
{
int nod = q.front();
q.pop();
if(nod == 2*n+1)
return true;
for(int i=1; i<=2*n+1; i++)
{
if(!visited[i] && capacity[nod][i] > 0)
{
q.push(i);
parent[i] = nod;
visited[i] = 1;
}
}
}
return false;
}
int main()
{
int a,b,c;
fin>>n;
visited.resize(2*n+2, 0);
parent.resize(2*n+2, 0);
//setam capacitatile pentru intrare si iesire
for(int i=1; i<=n; i++)
{
fin>>a>>b;
capacity[0][i] = a;
capacity[n+i][2*n+1] = b;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
capacity[i][n+j] = 1;
}
capacity[i][n+i] = 0;
}
int reusit = bfs();
while(reusit)
{
for(int i=1; i<=n; i++)
{
if(visited[n+i])
{
parent[2*n+1] = n+i;
flow = INT_MAX;
for(int j=2*n+1; j!=0; j=parent[j])
{
flow=min(flow, capacity[parent[j]][j]);
}
if(flow != 0)
{
for(int j=2*n+1; j!=0; j=parent[j])
{
capacity[parent[j]][j] -= flow;
capacity[j][parent[j]] += flow;
}
max_flow += flow;
}
}
}
reusit = bfs();
}
fout<<max_flow<<'\n';
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i != j && capacity[i][n+j] == 0)
fout<<i<<' '<<j<<'\n';
}
}
return 0;
}