65 条题解
-
0
txyx LV 10 @ 2009-08-30 10:23:58
匈牙利算法
bool can(int x)
{
for (int i=1; i -
0
-
0
w122185976 LV 10 @ 2009-08-04 21:45:48
我真郁闷啊!PUPPY超了三个点,无输出.6K一下就过了!
还有就是要把V数组清空,不然只有十分! -
0
zhengfangyi LV 10 @ 2009-07-30 21:47:54
被数据鄙视了!!!!
一开始用链表写SAP,死活只有60.
后来怒了,改回数组,立刻0msAC.
不解,望大牛指点... -
0
var n,m,x,y,hh,ll,xx,yy,time,max,ha:longint;
a:array[1..1000,1..1000] of char;
h,l:array[1..1000] of integer;
flg:boolean;
begin
readln(n,m);
hh:=0;
ll:=0;for x:= 1 to n do
begin
for y:= 1 to m do
begin
read(a[x,y]);
if a[x,y] = '1' then
begin
if h[x] = 0 then inc(hh);
if l[y] = 0 then inc(ll);
inc(h[x]);
inc(l[y]);
end;
end;
readln;
end;time:=0;
repeat
max:=0;
for x:= 1 to n do
if h[x] > max then begin max:=h[x] ; xx:=x; ha:=1; end;
for x:= 1 to m do
if l[x] > max then begin max:=l[x] ; xx:=x; ha:=2; end;if ha= 1 then
begin
h[xx]:=0;
inc(time);
for x:= 1 to m do
if a[xx,x] = '1' then begin dec(l[x]); a[xx,x]:='0'; end;
end;if ha= 2 then
begin
l[xx]:=0;
inc(time);
for x:= 1 to n do
if a[x,xx] = '1' then begin dec(h[x]); a[x,xx]:='0'; end;
end;flg:=true;
for x:= 1 to n do
for y:= 1 to m do
if a[x,y] = '1' then flg:=false;until flg;
if hh > ll then hh:=ll;
if hh > time then hh:=time;
writeln(hh);end.
先统计有多少行有1
再统计有多少列有1
取最小值
再贪心一变
再取最小值可以过9组........
-
0
LV 0 @ 2009-02-07 12:43:53
二分图
左边是行，右边是列，如果a是点，就把i和j连上，然后求这个图的最大匹配。因为最大匹配等于最小顶点覆盖。输入第一个是行，第二个是列
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
txyx
LV 10
@ 2009-08-30 10:23:58
