Pagini recente » Rating Andrei Munteanu (andreimuteanu00) | Cod sursa (job #2869976) | Statistici Mihai Dumitrescu (dumiim) | Cod sursa (job #266957) | Cod sursa (job #1209531)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> L[1000];
int n,i,j,a,b,s,c[1010][1010],x[1010][1010],v[10010],t[10010],q[10010],p,u,vmin,sum;
FILE *f,*g;
int bfs(){
int a,i;
memset(v,0,sizeof(v));
p=u=1;
q[0]=0;
v[0]=1;
t[0]=-1;
while(p<=u){
a=q[p];
for(i=0;i<L[a].size();i++){
if(v[L[a][i]]==0&&c[a][L[a][i]]>x[a][L[a][i]]){
q[++u]=L[a][i];
v[L[a][i]]=1;
t[L[a][i]]=a;
}
}
p++;
}
return v[s];
}
int main(){
f=fopen("harta.in","r");
g=fopen("harta.out","w");
fscanf(f,"%d",&n);
s=2*n+1;
for(i=1;i<=n;i++){
fscanf(f,"%d%d",&a,&b);
L[0].push_back(i);
L[i].push_back(0);
c[0][i]=a;
for(j=n+1;j<=n*2;j++){
if(j-n!=i){
L[i].push_back(j);
L[j].push_back(i);
c[i][j]=1;
}
}
j=i+n;
L[j].push_back(s);
L[s].push_back(j);
c[j][s]=b;
}
while(bfs()){
for(i=0;i<L[s].size();i++){
a=L[s][i];
if(v[a]==1&&c[a][s]>x[a][s]){
vmin=c[a][s]-x[a][s];
while(t[a]!=-1){
if(c[t[a]][a]-x[t[a]][a]<vmin)
vmin=c[t[a]][a]-x[t[a]][a];
a=t[a];
}
a=L[s][i];
x[a][s]+=vmin;
x[s][a]-=vmin;
while(t[a]!=-1){
x[t[a]][a]+=vmin;
x[a][t[a]]-=vmin;
a=t[a];
}
sum+=vmin;
}
}
}
fprintf(g,"%d\n",sum);
for(i=1;i<=n;i++){
for(j=n+1;j<=2*n;j++){
if(x[i][j]==1)
fprintf(g,"%d %d\n",i,j-n);
}
}
fclose(f);
fclose(g);
return 0;
}