Pagini recente » Cod sursa (job #191387) | Cod sursa (job #2086742) | Cod sursa (job #1326435) | Cod sursa (job #1020599) | Cod sursa (job #2456358)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N=200+7;
struct dumbFlow {
int n;
int cap[N][N];
int par[N];
vector <int> g[N];
bool vis[N];
void AddEdge(int a, int b, int c) {
cap[a][b] += c;
g[a].push_back(b);
g[b].push_back(a);
}
bool BFS() {
for (int i = 1; i <= n; i++) {
vis[i] = 0;
}
queue <int> Q;
Q.push(1);
while (!Q.empty()) {
int nod = Q.front();
Q.pop();
if (nod == n) {
continue;
}
for (auto &nou : g[nod]) {
if (!vis[nou] && cap[nod][nou]) {
vis[nou] = 1;
par[nou] = nod;
Q.push(nou);
}
}
}
return vis[n];
}
int maxFlow() {
int flow = 0;
while (BFS()) {
for (auto &nod : g[n]) {
if (vis[nod]) {
int curNode = nod, curMin = cap[nod][n];
while (curMin > 0 && curNode != 1) {
curMin = min(curMin, cap[par[curNode]][curNode]);
curNode = par[curNode];
}
if (curMin > 0) {
flow += curMin;
int curNode = nod;
while (curNode != 1) {
cap[par[curNode]][curNode] -= curMin;
cap[curNode][par[curNode]] += curMin;
curNode = par[curNode];
}
cap[nod][n] -= curMin;
cap[n][nod] += curMin;
}
}
}
}
return flow;
}
};
dumbFlow fl;
int n;
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
cin>>n;
fl.n=2*n+2;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
fl.AddEdge(1,i+1,x);
fl.AddEdge(i+n+1,2*n+2,y);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
fl.AddEdge(i+1,j+n+1,1);
cout<<fl.maxFlow()<<"\n";
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && fl.cap[i+1][j+n+1]==0)
cout<<i<<" "<<j<<"\n";
return 0;
}