Pagini recente » Cod sursa (job #2101671) | Cod sursa (job #2805225) | Cod sursa (job #1735557) | Cod sursa (job #1108318) | Cod sursa (job #2663078)
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <cstring>
#define dim 110
using namespace std;
vector <int> a[dim];
queue<int> c;
int f[dim];
int t[dim];
int cost[dim][dim];
int flux[dim][dim];
int iesire[dim];
int intrare[dim];
int i,j,n,m,Min,sol,nod,vecin;
int bfs() {
for (;!c.empty();c.pop())
memset (f,0,sizeof(f));
c.push(0);
f[0]=1;
while (!c.empty()) {
int nod=c.front();
for (int i=0;i<a[nod].size();i++) {
int vecin=a[nod][i];
if (cost[nod][vecin]>flux[nod][vecin]&&f[vecin]==0) {
f[vecin]=1;
c.push(vecin);
t[vecin]=nod;
if (vecin==2*n+1) {
return 1;
}
}
}
c.pop();
}
return 0;
}
int main() {
ifstream fin("harta.in");
ofstream fout("harta.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>iesire[i]>>intrare[i];
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
if (i==j) continue;
a[i].push_back(n+j);
a[n+j].push_back(i);
cost[i][n+j]=1;
}
}
for (i=1;i<=n;i++) {
a[0].push_back(i);
a[i].push_back(0);
cost[0][i]=intrare[i];
}
for (i=n+1;i<=2*n;i++) {
a[2*n+1].push_back(i);
a[i].push_back(2*n+1);
cost[i][2*n+1]=iesire[i-n];
}
while (bfs()) {
t[0]=-1;
Min=INT_MAX;
for (i=2*n+1;t[i]!=-1;i=t[i]) {
Min=min(Min,cost[t[i]][i]-flux[t[i]][i]);
}
sol+=Min;
for (i=2*n+1;t[i]!=-1;i=t[i]) {
flux[t[i]][i]+=Min;
flux[i][t[i]]-=Min;
}
}
fout<<sol<<"\n";
for (nod=1;nod<=n;nod++) {
for (i=0;i<a[nod].size();i++) {
vecin=a[nod][i];
if (flux[nod][vecin]==1&&vecin!=nod+n) {
fout<<nod<<" "<<vecin-n<<"\n";
}
}
}
return 0;
}