Pagini recente » Cod sursa (job #2908768) | Cod sursa (job #3250021) | Cod sursa (job #2673171) | Cod sursa (job #2825275) | Cod sursa (job #2961910)
#include <fstream>
#include <cstring>
#include <queue>
#define NRMAX 210
/**
-Construim un graf bipartit cu cele n noduri in ambele parti si vom adauga
o sursa si o destinatie. Costurile vor fi: muchie in graf bipartit - cost 1, muchie de la sursa la stanga - cost de intrare,
muchie de la dreapta la destinatie - cost de iesire
Daca suma gradelor de intrare difera de suma gradelor de iesire sau daca suma nu este egala cu fluxul maxim gasit inseamna ca nu avem solutie.
*/
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m,dad[NRMAX],total_in,total_out;
int capacitate[NRMAX][NRMAX];
bool viz[NRMAX],in_queue[NRMAX];
int BF()
{
queue<int> q;
q.push(0);
dad[0] = -1;
in_queue[0] = 1;
while(q.size())
{
int node = q.front();
q.pop();
if(viz[node]==1)
continue;
viz[node] = 1;
for(int i=0;i<=m;++i)
if(capacitate[node][i] > 0 )
if(in_queue[i]==0)
{
in_queue[i] = 1;
dad[i] = node;
q.push(i);
}
}
if(viz[m])
return 1;
return 0;
}
int main()
{
fin>>n; m=2*n+1;
for(int i=1;i<=n;++i)
{
int a,b;
fin>>a>>b;
capacitate[0][i] = a;
capacitate[n+i][m] = b;
total_in += a;
total_out += b;
}
for(int i=1;i<=n;++i)
for(int j=n+1;j<m;++j)
if(i != j-n)
capacitate[i][j] = 1;
while(BF())
{
for(int i=n+1;i<m;++i)
if(capacitate[i][m] && viz[i])
{
int actual_flow = capacitate[i][m], node = i;
while(node != 0)
{
actual_flow = min(actual_flow,capacitate[dad[node]][node]);
node = dad[node];
}
node = i , capacitate[node][m] -= actual_flow;
while(node != 0)
{
capacitate[dad[node]][node] -= actual_flow;
capacitate[node][dad[node]] += actual_flow;
node = dad[node];
}
}
memset(dad,0,sizeof(dad));
memset(viz,0,sizeof(viz));
memset(in_queue,0,sizeof(in_queue));
}
queue<pair<int,int> > edges;
for(int i=1;i<=n;++i)
for(int j=n+1;j<m;++j)
if(capacitate[j][i] > 0)
edges.push(make_pair(i,j-n));
int nr_edges = edges.size();
if(total_in != total_out || total_in != nr_edges)
{
fout<<"-1"<<"\n";
return 0;
}
fout<<nr_edges<<"\n";
while(edges.size())
{
int a = edges.front().first;
int b = edges.front().second;
edges.pop();
fout<<a<<" "<<b<<"\n";
}
fin.close();
fout.close();
//Complexitate: O(n*m^2), n = numar de varfuri, m = numar de muchii
return 0;
}