Pagini recente » Cod sursa (job #524328) | Cod sursa (job #2937910) | Cod sursa (job #2635796) | Cod sursa (job #2936336) | Cod sursa (job #475130)
Cod sursa(job #475130)
#include<fstream>
#include<queue>
using namespace std;
#define NMAX 203
ifstream fi("harta.in");
ofstream fo("harta.out");
int n,m,i,j,s,d,fmin;
int c[NMAX][NMAX],f[NMAX][NMAX],t[NMAX];
bool viz[NMAX],vec[NMAX][NMAX];
queue<int> q;
bool bfs() {
int nod,i;
q.push(s);
viz[s]=true;
for(i=1;i<=d;++i) viz[i]=false;
while(!q.empty()) {
nod=q.front();
q.pop();
if(nod==d) continue;
for(i=s;i<=d;++i)
if(!viz[i] && vec[nod][i] && f[nod][i]<c[nod][i]) {
t[i]=nod;
q.push(i);
viz[i]=true;
}
}
return viz[d];
}
int main() {
fi>>n;
d=n+n+1;
for(i=1;i<=n;++i) {
fi>>c[s][i]>>c[n+i][d];
m+=c[n+i][d];
}
for(i=1;i<=n;++i)
for(j=n+1;j<=n+n;++j)
if(i!=j) c[i][j]=1;
for(i=1;i<=n;++i) {
vec[s][i]=true;
vec[i][s]=true;
vec[n+i][d]=true;
vec[d][n+i]=true;
}
for(i=1;i<=n;++i)
for(j=n+1;j<=n+n;++j)
if(j-i!=n) {
vec[i][j]=true;
vec[j][i]=true;
}
while(bfs()) {
for(i=n+1;i<=n+n;++i)
if(viz[i] && f[i][d]<c[i][d]) {
t[d]=i;
fmin=c[i][d]-f[i][d];
for(j=d;j!=s;j=t[j])
fmin=min(fmin,c[t[j]][j]-f[t[j]][j]);
for(j=d;j!=s;j=t[j]) {
f[t[j]][j]+=fmin;
f[j][t[j]]-=fmin;
}
}
}
fo<<m<<"\n";
for(i=1;i<=n;++i)
for(j=n+1;j<=n+n;++j)
if(f[i][j]) fo<<i<<" "<<j-n<<"\n";
return 0;
}