Pagini recente » Cod sursa (job #3139097) | Cod sursa (job #526531) | Cod sursa (job #2425385) | Cod sursa (job #692798) | Cod sursa (job #2951231)
#include <iostream>
#include<fstream>
using namespace std;
int n;
int indeg[101],outdeg[101],up[205],queue[101];
int graf[202][202],insum,outsum,flow;
int augument(){
int head, tail;
for (int i = 0; i < 2 * n + 2; i++) {
queue[i] = 0;
up[i] = -1;
}
queue[0] = 0;
up[0] = 0;
for (head = tail = 0; head <= tail; head++){
int i = queue[head];
for (int j = 0; j < 2 * n + 2; j++)
if (graf[i][j] && up[j] == -1){
up[j] = i;
queue[++tail] = j;
if (j == 2 * n + 1) {
flow++;
return 1;
}
}
}
return 0;
}
void solve(){
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
if(i!=j)
graf[i][j+n] = 1;
while (augument())
for (int i = 2 * n + 1; i; i = up[i]) {
graf[up[i]][i]--;
graf[i][up[i]]++;
}
}
int main(){
ifstream fin("harta.in");
ofstream fout("harta.out");
fin >> n;
for(int i = 1;i <= n; ++i){
fin >> indeg[i] >> outdeg[i];
graf[0][i] = indeg[i];
graf[i + n][2 * n + 1] = outdeg[i];
insum += indeg[i];
outsum += outdeg[i];
}
if(insum != outsum)
fout << "-1\n";
solve();
if (flow < insum) {
fout<<"-1\n";
return 0;
}
fout<<flow;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (graf[j + n][i])
fout << i << " " <<j <<"\n";
return 0;
}