Pagini recente » Cod sursa (job #620418) | Cod sursa (job #2703159) | Cod sursa (job #2462022) | Cod sursa (job #2242837) | Cod sursa (job #2961328)
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int N,M;
int capacitate[1001][1001];
vector<vector<int>> adj;
int element, nod, flux_maxim, flux_minim, firstelem;
vector<int> tata;
vector<bool> vizitat;
queue<int> coada;
#define M 2*N+1
int creare_lant()
{
while(!coada.empty()) coada.pop();
tata.clear();
tata.resize(M+1,0);
vizitat.clear();
vizitat.resize(M+1,false);
coada.push(0);
vizitat[0]=true;
while(!coada.empty())
{
firstelem=coada.front();
coada.pop();
for(auto p:adj[firstelem])
{
if(vizitat[p]==false && capacitate[firstelem][p]>0)
{
coada.push(p);
vizitat[p]=true;
tata[p]=firstelem;
if(p==M) return 1;
}
}
}
return 0;
}
void calcul_flux()
{
for(auto p:adj[N])
if(vizitat[p]==true)
{
element = M;
flux_minim=INT_MAX;
while (element!=0) // caut care este fluxul minim cu care poate fi modificat lantul curent
{
nod = tata[element];
if(flux_minim > capacitate[nod][element])
flux_minim = capacitate[nod][element];
element = nod;
}
element = M;
while (element!=0) // dupa ce am aflat fluxul minim, actualizez fluxurile
{
nod = tata[element];
capacitate[nod][element] -= flux_minim;
capacitate[element][nod] += flux_minim;
element = nod;
}
flux_maxim = flux_maxim + flux_minim;
}
}
int main()
{
f>>N;
adj.resize(M+1);
int grad1, grad2;
for(int i=1;i<=N;i++)
{
adj[0].push_back(i);
adj[i].push_back(0);
adj[N+i].push_back(M);
adj[M].push_back(N+1);
f>>grad1>>grad2;
capacitate[0][i]=grad1;
capacitate[N+i][M]=grad2;
for(int j=N+1;j<=M-1;j++) // cream legaturi intre toate nodurile si duplicatele
{
if(j-i!=N) // cu exceptia legaturii dintre nodului curent si duplicatul sau
{
adj[i].push_back(j);
adj[j].push_back(i);
capacitate[i][j]=1;
}
}
}
flux_maxim=0;
while (creare_lant())
{
calcul_flux();
}
g<<flux_maxim<<'\n';
for(int i=1;i<=N;i++)
{
for(int j=N+1;j<=M;j++)
if (capacitate[j][i]==1)
{
g<<i<<' '<< j-N<< '\n';
}
}
}