Pagini recente » Cod sursa (job #163853) | Cod sursa (job #364854) | Cod sursa (job #1998866) | Cod sursa (job #2790445) | Cod sursa (job #1164421)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define minim(a,b) (a<b)?(a):(b)
#define nmax 105
using namespace std;
vector <int> g[nmax];
vector <int> r[nmax];
queue <int> q;
int cap[2*nmax][2*nmax];
int flow[2*nmax][2*nmax];
int input[nmax];
int output[nmax];
int t[nmax];
int n,m;
int maxflow;
bool bfs() {
bool found = false;
memset(t,-1,nmax*4);
t[0] = -2;
q.push(0);
while (!q.empty()) {
int ct = q.front(); q.pop();
for (vector <int> :: iterator it = g[ct].begin();it != g[ct].end();it++) {
if (cap[ct][*it] - flow[ct][*it] > 0 && t[*it] == -1) {
if (*it != n+n+1) {
q.push(*it);
t[*it] = ct;
} else {
found = true;
}
}
}
}
return found;
}
int getMin(int x) {
if (t[x] >= 0) {
int newMin = getMin(t[x]);
return minim(newMin,cap[t[x]][x] - flow[t[x]][x]);
}
return 0x3fffffff;
}
void update(int x,int value) {
if (t[x] >= 0) {
r[t[x]].push_back(x-n);
flow[t[x]][x] += value;
flow[x][t[x]] -= value;
update(t[x],value);
}
}
int main() {
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d %d",&output[i],&input[i]);
cap[0][i] = output[i];
cap[i+n][n+n+1] = input[i];
g[0].push_back(i);
g[i].push_back(0);
g[i+n].push_back(n+n+1);
g[n+n+1].push_back(i+n);
}
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j && output[i] && input[j]) {
g[i].push_back(j+n); g[j+n].push_back(i);
cap[i][j+n] = 1;
}
while (bfs()) {
for (vector <int> :: iterator it = g[n+n+1].begin(); it != g[n+n+1].end();it++) {
t[n+n+1] = *it;
int ct = n+n+1;
if (cap[*it][n+n+1] > flow[*it][n+n+1] && t[*it] >= 0) {
int min = getMin(n+n+1);
if(min <= 0) continue;
maxflow += min;
update(n+n+1,min);
}
}
}
printf("%d\n",maxflow);
for (int i=1;i<=n;i++) {
for(int j =1; j<=n;j++)
if(flow[i][n+j] == 1 )
printf("%d %d\n",i,j);
}
return 0;
}