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