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

Re:每次找有最多1的行或列,然后删除此行/列上的所有1,然后再来...

Posted by ceshihao at 2008-08-28 00:47:48 on Problem 3041
In Reply To:Re:每次找有最多1的行或列,然后删除此行/列上的所有1,然后再来... Posted by:lzpsky at 2007-03-13 16:16:18
真的会超时吗?邻接矩阵匈牙利的复杂度是O(N^3)对吗?这样贪心不也是O(N^3)吗?可是我WA了,大牛们帮忙看下是为什么?这个贪心策略有问题吗?

#include<stdio.h>
#include<string.h>

int n,m,a[501][501],pos;

void init()//生成邻接矩阵
{int i,j,x,y;
 memset(a,0,sizeof(a));
 for(i=1;i<=m;i++)
    {scanf("%d %d",&x,&y);
     a[x][y]=1;
    }
}

int findmax()//找最大,找到的位置存在全局变量pos,返回type 
{int max=0;
 int i,j,sum,type=0;//type=0说明没找到,1说明在行中找到,2说明在列中找到 
 for(i=1;i<=n;i++)//统计行 
    {sum=a[i][1];
     for(j=2;j<=n;j++)
        {sum+=a[i][j];
        }
     if(sum>max)
        {max=sum;
         pos=i;
         type=1;
        }
    }

 for(j=1;j<=n;j++)//统计列 
    {sum=a[1][j];
     for(i=2;i<=n;i++)
        {sum+=a[i][j];
        }
     if(sum>max)
        {max=sum;
         pos=j;
         type=2;
        }
    }
 return type; 
}

int count()//统计 
{int i,j,sum=0;
 while(findmax()!=0)//若还有不为零的元素 
      {sum++;
       if(findmax()==1)
         {for(j=1;j<=n;j++)//删行 
             a[pos][j]=0;
         }
       else
         {for(i=1;i<=n;i++)//删列 
             a[i][pos]=0;
         }         
      }
 return sum;//返回炮数 
}

int main()
{//freopen("in.txt","r",stdin);
 while(scanf("%d %d",&n,&m)!=EOF)
      {init();
       printf("%d\n",count());
      }
 //while(1);
 return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator