讨论 / 怎么做啊?
qdzcslj 2012-08-08 06:05:00
点我顶贴 收藏 删除
深搜超时40分,难道用动归,大牛指导一下阿?

#1 fjxmlhx@2008-05-24 20:05:00
回复 删除
二分图最大匹配...

PS:DFS能40都不错了..

#2 whitegene@2008-05-25 00:33:00
回复 删除
这个题根本不用这么复杂.

#3 libojie@2008-05-30 04:09:00
回复 删除
二分图最大匹配。

匈牙利算法。

#4 renqing@2008-06-22 07:33:00
回复 删除
whitegene那个代码我看了之后很惊讶,发现自己白写了那么多行,不过如果whitegene:前10个人正好最多9个满足,而最后一个人2张都满足,那不就Ans=11了吗?正确应该10;所以说你那个方法有点cheat感觉。数据有点太弱了。

我用倒推法做的,第一次80分,然后修改了寻址顺序就成了100分了。。。

#5 weweweer9@2008-07-10 01:17:00
回复 删除
二分图最大匹配?

怎么做啊?

#6 lizhixin@2008-07-23 19:42:00
回复 删除
原来还有很多人不知道匈牙利啊
#7 wwww@2008-08-22 07:12:00
回复 删除
我是靠此代码第一个AC

var s:set of 1..255;

n,m,i,j,k,l,p1:integer;

begin

readln(n,m);

for i:=1 to n do

begin

read(p1);

for j:=1 to p1 do begin read(k);s:=s+[k];end;

end;

for i:=1 to 255 do if i in s then l:=l+1;

if l>n then write(n) else write(l);

end.

#8 barry@2012-08-08 06:05:00
回复 删除
回复 地壳wwww 的帖子

楼上霸气

#9 hchx@2013-12-28 05:04:45
回复 删除
var n,m,i,j,x,ans:longint;

g:array [1..100,0..300] of longint;

f,use:array [1..300] of boolean;

link:array [1..300] of longint;

function find(k:longint):boolean;

var i:longint;

begin

for i:=1 to g[k,0] do

if not(use[g[k,i]]) then

begin

use[g[k,i]]:=true;

if (link[g[k,i]]=0) or find(link[g[k,i]]) then

begin

link[g[k,i]]:=k;

exit(true);

end;

end;

exit(false);

end;

begin

read(n,m);

for i:=1 to n do

begin

read(g[i,0]);

fillchar(f,sizeof(f),false);

for j:=1 to g[i,0] do

begin

read(x);

f[x]:=true;

end;

x:=0;

for j:=1 to m do

if f[j] then

begin

x:=x+1;

g[i,x]:=j;

end;

end;

ans:=0;

fillchar(link,sizeof(link),0);

for i:=1 to n do

begin

fillchar(use,sizeof(use),false);

if find(i) then

inc(ans);

end;

writeln(ans);

end.

查看更多回复
提交回复