| ||||||||||
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:每次找有最多1的行或列,然后删除此行/列上的所有1,然后再来...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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator