Pagini recente » Cod sursa (job #1755080) | Cod sursa (job #1007142) | Cod sursa (job #1882712) | Cod sursa (job #1995018) | Cod sursa (job #1444432)
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <string>
using namespace std;
const int maxN = 100 + 100 + 2;
bool BFS(int src, int N, vector<int> adjList[],
int flow[][maxN], int capacity[][maxN], int parent[], bool visited[]);
int main()
{
int N, i, x, y, j;
ifstream f("harta.in");
f >> N;
int outer[N + 1], inner[N + 1], sumInner = 0, sumOuter = 0;
vector<int> adjList[maxN];
int flow[maxN][maxN], capacity[maxN][maxN], parent[maxN];
bool visited[maxN];
for (i = 0; i <= N + N + 1; i++)
{
fill(flow[i], flow[i] + maxN, 0);
fill(capacity[i], capacity[i] + maxN, 0);
}
//
for(i = 1; i <= N; i++)
{
f>>inner[i];
f>>outer[i];
sumInner += inner[i];
sumOuter += outer[i];
adjList[0].push_back(i);
adjList[i].push_back(0);
capacity[0][i]=inner[i];
adjList[i + N].push_back(N + N + 1);
adjList[N + N + 1].push_back(i + N);
capacity[i + N][N + N + 1]=outer[i];
}
f.close();
//!
for(i = 1; i <= N; i++)
for(j = i + 1; j <= N; j++)
{
adjList[i].push_back(j + N);
adjList[j + N].push_back(i);
capacity[i][j + N] = 1;
adjList[j].push_back(i + N);
adjList[i + N].push_back(j);
capacity[j][i + N] = 1;
}
int minFlow, result = 0;
int currentNode;
while (BFS(0, N + N + 1, adjList, flow, capacity, parent, visited))
{
for (j = 0; j < adjList[N + N + 1].size(); j++)
{
currentNode = adjList[N + N + 1][j];
if (flow[currentNode][N + N + 1] != capacity[currentNode][N + N + 1] && visited[currentNode])
{
minFlow = INT_MAX;
parent[N + N + 1] = currentNode;
for (i = N + N + 1; parent[i] != -1; i = parent[i])
minFlow = min(minFlow, capacity[parent[i]][i] - flow[parent[i]][i]);
if (minFlow)
{
for (i = N + N + 1; parent[i] != -1; i = parent[i])
{
flow[parent[i]][i] += minFlow;
flow[i][parent[i]] -= minFlow;
}
result += minFlow;
}
}
}
}
ofstream g("harta.out");
if (result != sumInner)
g << "0";
else
{
g << result << '\n';
for (i = 1; i <= N; i++)
for (j = N + 1; j <= N + N; j++)
if (flow[i][j] == 1)
g << i << " " << j - N << '\n';
}
g.close();
return 0;
}
bool BFS(int src, int N, vector<int> adjList[],
int flow[][maxN], int capacity[][maxN], int parent[], bool visited[])
{
fill(visited, visited + N + 1, false);
queue<int> q;
q.push(src);
visited[src] = true;
parent[src] = -1;
int x, i;
while (!q.empty())
{
x = q.front();
q.pop();
if (x != N)
{
for (i = 0; i < adjList[x].size(); i++)
{
int neighbor = adjList[x][i];
if (capacity[x][neighbor] != flow[x][neighbor] && !visited[neighbor])
{
visited[neighbor] = true;
q.push(neighbor);
parent[neighbor] = x;
}
}
}
}
return visited[N];
}