Pagini recente » Cod sursa (job #2828572) | Cod sursa (job #2700222) | Cod sursa (job #2930295) | Cod sursa (job #2683737) | Cod sursa (job #2962131)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> graf, rgraf;
vector<int> parent;
int n, dest, x,y;
void citire()
{
fin >> n;
//sursa=0;
dest= 2 * n + 1;
graf.resize(201);
rgraf.resize(201, vector<int>(201));
parent.resize(2 * n + 1);
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
if(i != j- n)
{
rgraf[i][j]=1;
graf[i].push_back(j);
graf[j].push_back(i);
}
for(int i=1; i <= n; i++)
{
fin >> x >> y;
graf[0].push_back(i);
graf[i].push_back(0);
graf[dest].push_back(i + n);
graf[i + n].push_back(dest);
rgraf[0][i]=x;
rgraf[i + n][dest]=y;
}
}
bool bfs()
{
vector<bool> viz(2 * n + 1, false);
queue<int> q;
q.push(0);
viz[0] = true;
parent[0] = -1;
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto ad: graf[nod])
if(viz[ad] == false && rgraf[nod][ad] != 0)
{
parent[ad] = nod; //tine minte drumul
if (ad == dest)
return true;
viz[ad] = true;
q.push(ad);
}
}
return false;
}
int fordf()
{
int flowtotal=0;
while(bfs())
{
int u, v=dest, pathflow = INT_MAX;
//sursa=0
while(v != 0)
{
u = parent[v];
if(rgraf[u][v] < pathflow)
pathflow= rgraf[u][v];
v = u;
}
v=dest;
while(v != 0)
{
u = parent[v];
rgraf[u][v] -= pathflow;
rgraf[v][u] += pathflow;
v = u;
}
flowtotal += pathflow;
}
return flowtotal;
}
int main()
{
citire();
fout << fordf()<<endl;
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
if(rgraf[j][i])
fout << i << " " << j - n << "\n";
return 0;
}