Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:第一题匈牙利二分图In Reply To:Re:第一题匈牙利二分图 Posted by:guyindu at 2016-01-06 13:35:31 wa,哪里错了? > #include<cstdio> > #include<cstdlib> > #include<cstring> > using namespace std; > > bool xihuan[405][405]; > int dui[405][405],dui1[405][405]; > > bool zhao(int x,int y,int lx,int ly) > { > if(xihuan[x][y-1] && y>1 && y-1!=ly) > { > if(dui[x][y-1]==0) > { > dui[x][y]=x; > dui1[x][y]=y-1; > dui[x][y-1]=x; > dui1[x][y-1]=y; > return true; > } > if(zhao(dui[x][y-1],dui1[x][y-1],x,y-1)&&(dui[x][y-1]!=lx || dui1[x][y-1]!=ly)) > { > dui[x][y]=x; > dui1[x][y]=y-1; > dui[x][y-1]=x; > dui1[x][y-1]=y; > return true; > } > } > if(xihuan[x-1][y] && x>1 && x-1!=lx) > { > if(dui[x-1][y]==0) > { > dui[x][y]=x-1; > dui1[x][y]=y; > dui[x-1][y]=x; > dui[x-1][y]=y; > return true; > } > if(zhao(dui[x-1][y],dui1[x-1][y],x-1,y)&&(dui[x-1][y]!=lx || dui1[x-1][y]!=ly)) > { > dui[x][y]=x-1; > dui1[x][y]=y; > dui[x-1][y]=x; > dui1[x-1][y]=y; > return true; > } > } > return false; > } > > int main() > { > int T,n,m;char c; > scanf("%d",&T); > for(int p=1;p<=T;p++) > { > scanf("%d %d",&n,&m); > memset(xihuan,false,sizeof(xihuan)); > for(int i=1;i<=n;i++) > { > scanf("\n"); > for(int j=1;j<=m;j++) > { > scanf("%c",&c); > if(c=='*') xihuan[i][j]=true; > } > } > int ans=0; > memset(dui,0,sizeof(dui)); > memset(dui1,0,sizeof(dui1)); > for(int i=1;i<=n;i++) > for(int j=1;j<=m;j++) > if(xihuan[i][j]) > { > //printf("%d %d\n",i,j); > if(zhao(i,j,i,j)) ans++; > } > for(int i=1;i<=n;i++) > for(int j=1;j<=m;j++) > if(xihuan[i][j] && dui[i][j]==0) ans++; > printf("%d\n",ans); > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator