Cod sursa(job #1209531)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 17 iulie 2014 23:08:27
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#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;
}