| ||||||||||
| 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