Pagini recente » Cod sursa (job #2848242) | Cod sursa (job #699503) | Cod sursa (job #1220019) | Rating Andrei Candet (gandacbucatarie) | Cod sursa (job #2616497)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
vector<int> adj[210];
vector<int> sol[110];
int n;
int c[210][210];
int in[110];
int out[110];
int parent[110];
int bfs(int s,int d)
{
queue<int> q;
bool visited[1010];
memset(visited, 0, sizeof (visited));
q.push(s);
parent[s]=s;
int current;
visited[0]=1;
while(!q.empty()) {
current=q.front();
q.pop();
if(current != d)
for(int nextNode : adj[current])
{
if(!visited[nextNode] && c[current][nextNode])
{
visited[nextNode]=1;
parent[nextNode]=current;
q.push(nextNode);
}
}
}
return visited[d];
}
int main()
{
in>>n;
int i,j;
for (i = 1; i <= n; i++)
in >> out[i] >> in[i];
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
{
c[i][100+j] = 1;
adj[i].push_back(100 + j);
adj[100 + j].push_back(i);
}
for (i = 1; i <= n; i++)
{
adj[0].push_back(i);
adj[i].push_back(0);
c[0][i] = out[i];
c[100 + i][100 + n + 1] = in[i];
adj[100 + i].push_back(100 + n + 1);
adj[100 + n + 1].push_back(100 + i);
}
int current, maxim, flow = 0;
while (bfs(0,100 + n + 1))
{
for (int i = 1; i <=n ; i++)
if (parent[100 + i] && c[100 + i][100 + n + 1])
{
parent[100 + n + 1] = 100 + i;
current = 100 + n + 1;
maxim = 0x7fffffff;
while (current != parent[current])
{
if (maxim > c[parent[current]][current])
maxim = c[parent[current]][current];
current = parent[current];
}
flow += maxim;
current = 100 + n + 1;
while (current != parent[current])
{
c[current][parent[current]] += maxim;
c[parent[current]][current] -= maxim;
current = parent[current];
}
}
}
out << flow << '\n';
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (c[j+100][i])
out << i << ' ' << j << '\n';
in.close();
out.close();
return 0;
}