Pagini recente » Cod sursa (job #893775) | Cod sursa (job #788713) | Cod sursa (job #1267887) | Cod sursa (job #2120605) | Cod sursa (job #1830230)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 100;
const int MAXNODE = 2 * NMAX + 2;
vector<int> G[MAXNODE + 5];
int n, parent[MAXNODE + 5], cap[MAXNODE + 5][MAXNODE + 5], flow[MAXNODE + 5][MAXNODE + 5], dest;
bool use[MAXNODE + 5];
bool BFS(){
memset(use, 0, sizeof use);
queue<int> q;
int node, curr_node, i;
q.push(0);
use[0] = true;
while(!q.empty()){
node = q.front();
q.pop();
if(node == dest) continue;
for(i = 0; i < (int)G[node].size(); ++i){
curr_node = G[node][i];
if(!use[curr_node] && flow[node][curr_node] < cap[node][curr_node]){
q.push(curr_node);
use[curr_node] = true;
parent[curr_node] = node;
}
}
}
return use[dest];
}
int main()
{
int i, in, out, j, nr_ver = 0, node;
bool cnt;
fin>>n;
dest = 2 * n + 1;
for(i = 1; i <= n; ++i){
fin>> out >> in;
G[0].push_back(i);
G[i].push_back(0);
cap[0][i] = out;
G[n + i].push_back(dest);
G[dest].push_back(n + i);
cap[n + i][dest] = in;
nr_ver += in;
}
for(i = 1; i <= n; ++i){
for(j = 1; j <= n; ++j){
if(i != j){
G[i].push_back(n + j);
G[n + j].push_back(i);
cap[i][n + j] = 1;
}
}
}
while(BFS()){
for(i = 0; i < (int)G[dest].size(); ++i){
node = G[dest][i];
if(use[node] && flow[node][dest] < cap[node][dest]){
parent[dest] = node;
cnt = true;
for(j = dest; j != 0; j = parent[j]){
if(flow[parent[j]][j] == cap[parent[j]][j]){
cnt = false;
}
}
if(cnt){
for(j = dest; j != 0; j = parent[j]){
++flow[parent[j]][j];
--flow[j][parent[j]];
}
}
}
}
}
fout<< nr_ver << "\n";
for(i = 1; i <= n; ++i){
for(j = 1; j <= n; ++j){
if(flow[i][n + j] == 1){
fout<< i << " " << j << "\n";
}
}
}
return 0;
}