Pagini recente » Cod sursa (job #275520) | Cod sursa (job #867399) | Cod sursa (job #2142662) | Cod sursa (job #767365) | Cod sursa (job #2962475)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> adj;
int cap[2005][2005], tata[2005], n, m, s, t;
bool bfs()
{
queue <int> q;
vector <bool> vizitat(n * 2 + 2, false);
q.push(s);
vizitat[s] = true;
tata[s] = -1;
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto vecin : adj[nod])
{
if(!vizitat[vecin] && cap[nod][vecin] != 0)
{
tata[vecin] = nod;
if(vecin == t)
return true;
vizitat[vecin] = true;
q.push(vecin);
}
}
}
return false;
}
int maxflow() //Alg. Edmonds Karp
{
int maxim = 0;
while(bfs())
{
int b, a = t, flow = INT_MAX;
while(a != s)
{
b = tata[a];
if(cap[b][a] < flow)
flow = cap[b][a];
a = b;
}
a = t;
while(a != s)
{
b = tata[a];
cap[b][a] -= flow;
cap[a][b] += flow;
a = b;
}
maxim += flow;
}
return maxim;
}
int main()
{
int a, b, i, j;
f >> n;
t = n * 2 + 1; //sink
adj.resize(t+1);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(i != j)
{
adj[i].push_back(j+n);
adj[j+n].push_back(i);
cap[i][j+n] = 1;
}
}
f>>a>>b;
adj[s].push_back(i);
adj[i].push_back(s);
cap[s][i] = a;
adj[t].push_back(i+n);
adj[i+n].push_back(t);
cap[i+n][t] = b;
}
g << maxflow() << endl;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(cap[j+n][i] == 1)
g << i << " " << j << endl;
}
}
return 0;
}