Pagini recente » Cod sursa (job #2315912) | Cod sursa (job #2782857) | Cod sursa (job #2562118) | Cod sursa (job #49814) | Cod sursa (job #3190763)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define intmax INT_MAX
#define N 1002
int capacitate[N][N];
int flux[N][N];
vector<int> graf[N];
vector<int> tati;
int bfs(int s, int t)
{
deque<int> deq;
vector<int> viz(t+1,0);
tati.assign(t+1,0);
deq.push_back(s);
viz[s]=1;
while (deq.size()>0)
{
int nod=deq.front();
deq.pop_front();
if (nod==t)
break;
for (int i=0; i<graf[nod].size(); i++)
{
int vecin=graf[nod][i];
if (!viz[vecin])
{
if(capacitate[nod][vecin] - flux[nod][vecin] > 0)
{
deq.push_back(vecin);
tati[vecin]=nod;
viz[vecin]=1;
}
}
}
}
if (tati[t] != 0)
return 1;
return 0;
}
int edmond_karp(int s, int d)
{
int flow=0;
int mini;
while (bfs(s,d)) //cat timp sunt drumuri de crestere
{
mini=intmax;
int i=d;
while (i!=0)
{
if(capacitate[tati[i]][i] - flux[tati[i]][i] < mini)
mini = capacitate[tati[i]][i] - flux[tati[i]][i];
i = tati[i];
}
i = d;
while (i != 0)
{
flux[tati[i]][i] += mini;
flux[i][tati[i]] -= mini;
i = tati[i];
}
flow += mini;
}
return flow;
}
int main()
{
int n,s,t;
s=0;
f>>n;
t=2*n+1;
for (int i=1; i<=n; i++)
{
int x,y;
f>>x>>y;
int j=n+i;
graf[s].push_back(i);
graf[j].push_back(t);
capacitate[s][i]=x;
capacitate[j][t]=y;
}
for (int i=1; i<=n; i++)
for (int j=n+1; j<=2*n; j++)
if ((i%n)!=(j%n))
{
graf[i].push_back(j);
graf[j].push_back(i);
capacitate[i][j] = 1;
}
g<<edmond_karp(s,t)<<endl;
for (int i=1; i<=n; i++)
for (int j=n+1; j<=2*n; j++)
{
if (flux[i][j]==1)
g<<i<<" "<<j-n<<endl;
}
return 0;
}