Pagini recente » Cod sursa (job #492205) | Cod sursa (job #1904054) | Cod sursa (job #1843054) | Cod sursa (job #224247) | Cod sursa (job #3190879)
#include<iostream>
#include<fstream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<bitset>
#define INF 1e8
std::vector<std::vector<int>> capacitate, flow, adjList;
std::vector<int> parent;
std::vector<bool> visited;
int n, s, t, edges;
void readData()
{
std::ifstream fin("harta.in");
fin >> n;
t = 2 * n + 1;
s = 0;
adjList.resize(t + 2, {});
capacitate.resize(t + 2, std::vector<int>(t + 2));
flow.resize(t + 2, std::vector<int>(t + 2));
parent.resize(t + 2);
for (int i = 1; i <= n; i++)
{
int x, y;
fin >> x >> y;
edges += x;
adjList[s].push_back(i);
adjList[i].push_back(s);
adjList[n + i].push_back(t);
adjList[t].push_back(n + i);
capacitate[s][i] = x;
capacitate[n + i][t] = y;
}
fin.close();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i - j)
{
adjList[i].push_back(n + j);
adjList[n + j].push_back(i);
capacitate[i][n + j] = 1;
}
}
void afisareMatrice(std::vector<std::vector<int>> matrix)
{
for(int i = 0; i < matrix.size(); i++)
{
std::cout << i << ": ";
for(int j = 0; j < matrix[i].size(); j++)
std::cout << matrix[i][j] << ' ';
std::cout << '\n';
}
}
void bfs()
{
visited.assign(t, false);
std::queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (cur == t)
continue;
for (int urm : adjList[cur])
{
if (!visited[urm] && capacitate[cur][urm] != flow[cur][urm])
{
visited[urm] = true;
parent[urm] = cur;
q.push(urm);
}
}
}
}
void maxflow(int s, int t)
{
while (1)
{
bfs();
if (!visited[t])
break;
for (auto k : adjList[t])
{
if (!visited[k] || capacitate[k][t] == flow[k][t])
continue;
parent[t] = k;
int small = INF, node = t;
while (node != s)
{
small = std::min(small, capacitate[parent[node]][node] - flow[parent[node]][node]);
node = parent[node];
}
if (small)
{
node = t;
while (node != s)
{
flow[parent[node]][node] += small;
flow[node][parent[node]] -= small;
node = parent[node];
}
}
}
}
}
void afisareRes()
{
std::ofstream fout("harta.out");
fout << edges << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n ; j++)
if (i != j && capacitate[i][n + j] == flow[i][n + j])
fout << i << ' ' << j << '\n';
fout.close();
}
int main()
{
readData();
//afisareMatrice(adjList);
maxflow(s, t);
afisareRes();
}