讨论 / What's ?一样的代码····不一样的结果···还有,匈牙利算法超时,无语了
coldffire 2010-10-04 20:40:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: Xeond[6]

得分: 90分

提交日期: 2010-10-1 23:33:00

有效耗时: 1953毫秒

测试结果1: 通过本测试点|有效耗时421ms

测试结果2: 通过本测试点|有效耗时79ms

测试结果3: 通过本测试点|有效耗时218ms

测试结果4: 通过本测试点|有效耗时47ms

测试结果5: 通过本测试点|有效耗时360ms

测试结果6: 通过本测试点|有效耗时203ms

测试结果7: 通过本测试点|有效耗时281ms

测试结果8: 选手程序运行超过时限

测试结果9: 通过本测试点|有效耗时297ms

测试结果10: 通过本测试点|有效耗时47ms

===============================

状态: Unaccepted

测评机: Xeond[6]

得分: 80分

提交日期: 2010-10-1 23:32:00

有效耗时: 1703毫秒

测试结果1: 通过本测试点|有效耗时437ms

测试结果2: 通过本测试点|有效耗时94ms

测试结果3: 通过本测试点|有效耗时219ms

测试结果4: 通过本测试点|有效耗时46ms

测试结果5: 通过本测试点|有效耗时360ms

测试结果6: 通过本测试点|有效耗时203ms

测试结果7: 通过本测试点|有效耗时297ms

测试结果8: 选手程序运行超过时限

测试结果9: 测试结果错误.错误结果为:348

正确结果应为:344

测试结果10: 通过本测试点|有效耗时47ms

#define MM 1001

#include <iostream>

using namespace std;

int n,m,x,xx,t=0,a[MM][MM],f[MM][MM],b[MM],v[MM];

int paith(int i)

{

int j=1;

while(*(*(f+i)+j))

{

if(!b[*(*(f+i)+j)])

{

b[*(*(f+i)+j)]=1;

if(v[*(*(f+i)+j)]==0||paith(v[*(*(f+i)+j)]))

{

v[*(*(f+i)+j)]=i;

return 1;

}

}

j++;

}

return 0;

}

int main()

{

memset(v,0,sizeof(v));

memset(a,0,sizeof(a));

memset(f,0,sizeof(f));

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>xx;

for(int j=1;j<=xx;j++)

{

cin>>x;

a[i][x]=1;

}

}

for(int i=1;i<=n;i++)

{

int c=1;

for(int j=1;j<=n;j++)

if(!a[i][j]) f[i][c++]=j;

}

for(int i=1;i<=n;i++)

{

memset(b,0,sizeof(b));

if(paith(i)) t++;

}

cout<<t;

}

#1 noip2012@2010-10-04 20:40:00
回复 删除
用数组模拟邻接表

#2 fengchen123@2014-09-05 23:38:20
回复 删除
 用边表写呀!!!少了查找的复杂度
查看更多回复
提交回复