Pagini recente » Cod sursa (job #1567604) | Cod sursa (job #2026757) | Cod sursa (job #2872783) | Cod sursa (job #444938) | Cod sursa (job #165043)
Cod sursa(job #165043)
#include<stdio.h>
#include<memory.h>
#define inf 0x3f3f3f3f
int a[202][202],c[202][202],i,j,n,m,k,l,p,d[202],t[202],b[40002],s[202];
FILE *in,*out;
int drmin(){
int i,j,p,u,ok;
memset(s,0x0,sizeof(s));
for(i=0;i<=n+1;i++)
d[i]=inf;
d[0]=0;
p=u=1;b[1]=0;;
while(p<=u){
i=b[p++];
for(j=1;j<=n+1;j++)
if(i!=n+1&&c[i][j]==1&&d[j]>d[i]+a[i][j]){
d[j]=d[i]+a[i][j];
t[j]=i;
b[++u]=j;
}
}
return(d[n+1]);
}
int intoarce(){
int i=n+1;
while(i!=0){
c[t[i]][i]--;
c[i][t[i]]++;
i=t[i];
}
return(0);
}
int main(){
in=fopen("cc.in","rt");
out=fopen("cc.out","wt");
fscanf(in,"%d",&n);
//memset(a,0x7d00,sizeof(a));
//memset(c,0x2,sizeof(c));
m=(n<<1)+1;
for(i=0;i<=m;i++)
for(j=0;j<=m;j++){
c[i][j]=2;
a[i][j]=inf;
}
for(i=1;i<=n;i++){
a[0][i]=a[n+i][m]=0;
a[i][0]=a[m][n+i]=-1;
c[0][i]=c[n+i][m]=1;
c[i][0]=c[m][n+i]=0;
for(j=1;j<=n;j++){
fscanf(in,"%d",&l);
a[i][n+j]=l;
a[n+j][i]=-l;
c[i][n+j]=1;
c[n+j][i]=0;
}
}
n=n<<1;
m=0;
while((l=drmin())!=inf){
m+=l;
intoarce();
}
fprintf(out,"%d\n",m);
return(0);
}