Pagini recente » Cod sursa (job #2238987) | Joaca_3 | Cod sursa (job #1505390) | Cod sursa (job #1666492) | Cod sursa (job #1207058)
#include <fstream>
#include <vector>
#include<cstring>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int v[310],q[310],t[310],c[310][310],f[310][310];
int n,i,x,y,u,p,sol,minim,j,m;
vector <int> l[310];
int bfs() {
memset(v,0,sizeof(v));
v[0]=1;
t[0]=-1;
p=u=1;
q[1]=0;
while (p<=u) {
x=q[p];
for (int i=0;i<l[x].size();i++) {
y=l[x][i];
if (v[y]==0 && c[x][y]>f[x][y]) {
q[++u]=y;
t[y]=x;
v[y]=1;
}
}
p++;
}
return v[n];
}
int main () {
fin>>n;
for (i=1;i<=n;i++) {
fin>>x>>y;
l[0].push_back(i);
l[i].push_back(0);
c[0][i]=x;
for (j=n+1;j<=2*n;j++) {
if (j!=n+i) {
l[i].push_back(j);
l[j].push_back(i);
c[i][j]=1;
}
}
l[n+i].push_back(2*n+1);
l[2*n+1].push_back(n+i);
c[n+i][2*n+1]=y;
}
m=n;
n*=2;
n++;
while (bfs()) {
for (i=0;i<l[n].size();i++) {
x=l[n][i];
if (v[x]==1 && c[x][n]>f[x][n]){
minim=c[x][n]-f[x][n];
while (t[x]!=-1){
if (minim>c[t[x]][x]-f[t[x]][x])
minim=c[t[x]][x]-f[t[x]][x];
x=t[x];
}
x=l[n][i];
f[x][n]+=minim;
f[n][x]-=minim;
while (t[x]!=-1){
f[t[x]][x]+=minim;
f[x][t[x]]-=minim;
x=t[x];
}
sol+=minim;
}
}
}
fout<<sol<<"\n";
for (i=1;i<=m;i++)
for (j=m+1;j<=2*m;j++)
if (f[i][j]==1)
fout<<i<<" "<<j-m<<"\n";
return 0;
}