Pagini recente » Cod sursa (job #559206) | Cod sursa (job #1163599) | Cod sursa (job #270689) | Cod sursa (job #3179813) | Cod sursa (job #2962759)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define cin f
#define cout g
// the matrix capacity stores the residual network capacity
int n;
vector<int> parent;
vector<unordered_map<int, int>> capacity;
vector<unordered_map<int, int>> adj;
bool bfs(int s, int t)
{
fill(parent.begin(), parent.end(), -1);
parent[s] = -2;
queue<int> Q;
Q.push(s);
while(! Q.empty())
{
int cur = Q.front();
Q.pop();
for(auto &edge : capacity[cur])
{
if(parent[edge.first] == -1 and edge.second != 0)
{
parent[edge.first] = cur;
if(edge.first == t)
return true;
Q.push(edge.first);
}
}
}
return false;
}
int maxflow(int s, int t)
{
int flow = 0;
while(bfs(s, t))
{
for(auto &edge : capacity[t])
{
int cur = edge.first;
if(capacity[cur][t] == 0 || parent[cur] == -1)
continue;
int new_flow = INT_MAX;
new_flow = min(new_flow, capacity[cur][t]);
while(cur != s)
{
int prev = parent[cur];
new_flow = min(new_flow, capacity[prev][cur]);
if(new_flow == 0)
break;
cur = prev;
}
if(new_flow == 0)
continue;
flow += new_flow;
cur = edge.first;
capacity[cur][t] -= new_flow;
capacity[t][cur] += new_flow;
while(cur != s)
{
int prev = parent[cur];
capacity[prev][cur] -= new_flow;
capacity[cur][prev] += new_flow;
cur = prev;
}
}
}
return flow;
}
int main()
{
cin >> n;
parent.resize(n * 2 + 3);
capacity.resize(n * 2 + 3);
adj.resize(n * 2 + 3);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
{
adj[i][j + n] = 1;
capacity[i][j + n] = 1;
capacity[j + n][i] = 0;
}
int s, t;
s = n * 2 + 1, t = n * 2 + 2;
for(int i = 1; i <= n; i++)
{
int in, out;
cin >> in >> out;
adj[s][i] = in;
capacity[s][i] = in;
capacity[i][s] = 0;
adj[i + n][t] = out;
capacity[i + n][t] = out;
capacity[t][i + n] = 0;
}
cout<<maxflow(s, t)<<'\n';
for(int i = 1; i <= n; i++)
for(auto it : adj[i])
if(capacity[i][it.first] == 0)
cout<<i<<' '<<it.first - n<<'\n';
return 0;
}