Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:太诡异了这个题……两份代码对于一个测试数据，结果不一样，可是都AC了……这是什么世道？为什么我的WA？继续调试

Posted by lenglengmajia at 2009-03-24 15:00:46 on Problem 2195
In Reply To:太诡异了这个题……两份代码对于一个测试数据，结果不一样，可是都AC了……这是什么世道？为什么我的WA？继续调试 Posted by:lenglengmajia at 2009-03-24 14:58:51
```#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
struct node{
int r,c;
}man[10001],home[10001];
int r,c,num_of_man,num_of_home,map[101][101],lx[101],ly[101],match[101];
bool visx[101],visy[101];

int dfs(int t){//寻找完备匹配
int i,tmp;
visx[t]=true;
for(i=1;i<=num_of_home;i++){
if(!visy[i] && lx[t]+ly[i]==map[t][i]){
tmp=match[i];
visy[i]=true;
match[i]=t;
if(tmp==0 || dfs(tmp)) return 1;
match[i]=tmp;
}
}
return 0;
}

int main(){
while(scanf("%d%d",&r,&c),r&&c){
getchar();
int i,j,k; char a;
num_of_home=0;num_of_man=0;
for(j=1;j<=c;j++){
if((a=getchar())=='m'){
man[++num_of_man].r=i;
man[num_of_man].c=j;
}
else if(a=='H'){
home[++num_of_home].r=i;
home[num_of_home].c=j;
}
}
getchar();
}
//printf("%d %d\n",num_of_man,num_of_home);
memset(map,0,sizeof(map));
for(i=1;i<=num_of_man;i++){
for(j=1;j<=num_of_home;j++){
map[i][j]=(int )fabs(man[i].r-home[j].r)+(int )fabs(man[i].c-home[j].c);
}
}
memset(lx,127,sizeof(lx));
memset(ly,0,sizeof(ly));
for(i=1;i<=num_of_man;i++){
for(j=1;j<=num_of_home;j++){
if(map[i][j]<lx[i]) lx[i]=map[i][j];//如果是最大权值匹配 则初始值顶标取最大值
}                                       //若是最小匹配则取最小值
}
//KM algorithm
memset(match,0,sizeof(match));
for(i=1;i<=num_of_man;i++){//
while(1){
memset(visx,0,sizeof(visx));//清零
memset(visy,0,sizeof(visy));
int min=10000000;
if(dfs(i)) break;//寻找完备匹配
for(j=1;j<=num_of_man;j++){//找出 min=1000000;x搜索树上y不在搜索树上边
if(visx[j])            //找出顶标最大能改进的d值
for(k=1;k<=num_of_home;k++){
if(!visy[k] && map[j][k]-lx[j]-ly[k]<min)//基于 lx[i]+ly[j]<=map[i][j] 找出map[j][k]-lx[j]-ly[k]的最小值 d
min=map[j][k]-lx[j]-ly[k];           //若是最大匹配则应满足 lx[i]+ly[j]>=map[i][j] 找出
}                                            //lx[i]-ly[j]-map[i][j]的最小值 d
}
for(j=1;j<=num_of_man;j++) if(visx[j]) lx[j]+=min;//用d来改进搜索树上各点的顶标
for(j=1;j<=num_of_home;j++) if(visy[j]) ly[j]-=min; //
}
}
int sum=0;
for(i=1;i<=num_of_home;i++) sum+=map[match[i]][i];
printf("%d\n",sum);
}
return 0;
}

Followed by: