编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一道不错的网络流题，拆点吧，会两个的，拆三个的不理解.......这就是我和大牛之间的差距吧。

Orz那个贪心的算法，真的很强大。

编译通过...

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

?

先ORZ ZKK同学不拆点的方法 。。。

只想到拆点的 写写看先。。

我靠 输入数据行末有个无耻的空格！！！！！！！！

1晚上就被这样流过去了。。

拆点方案如下 。。。还是比较好想的

for (int i = 1; i

program li;

var n,min,k,i,j:longint;

s:array[0..1500] of string;

boy,gril:array[0..1500] of longint;

begin

readln(n,k);

for i:= 1 to n do readln(s[i]);

for i:= 1 to n do begin boy[i]:=0; gril[i]:=0; end;

for i:= 1 to n do

for j:= 1 to n do

if s[i][j]='Y' then

begin inc(boy[i]); inc(gril[j]); end;

min:=maxlongint;

for i:= 1 to n do

if min>boy[i] then min:=boy[i];

for i:= 1 to n do

if min>gril[i] then min:=gril[i];

if min+k>n then writeln(n)

else writeln(min+k);

end.

大牛们方法我看不懂............网络流..拆点...不会

我把程序放在了

http://hi.baidu.com/cloudygoose/blog/item/a8e78b39bda6d92db9998ff5.html

先ORZ BOYZKK啊

不拆点的方法

2n个点+二分答案即可,轻松秒杀

点击我查看题解

有点弱...不过这题最哈袄的方法竟然不是sap或其他,最好的方法是最为朴素距离标号...这样方便增广(由于题目数据弱,所以....)若题目数据恐怖,每次不是枚局,而应该是加大limit,然后一次O(N^2)的增广

拆点就OK了。不过我搞了6*n+2个点，不爽！！！

感觉这题很诡异，把数组开到302就WA两个点，开到600就AC了

看来一定要把数组开得足够大

感谢voyagec2神牛的方法

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我的方法有点烦了，要枚举答案。

设当前枚举到的答案为limit，将男孩和女孩各拆成三个（0号、1号和2号）。

设源点为s，汇点为t。

连s到每个男孩的0号，容量为limit，男孩的0号连到1号和2号，1号容量∞，2号容量为k。

如果是喜欢男孩i喜欢女孩j，则从男孩i的1号连到女孩j的1号，否则从男孩i的2号连到女孩j的2号。

对于每个女孩，1号连到0号，容量为∞，2号再连到0号，容量为k。然后0号连到t，容量为limit。

如果最大流为limit*n，则当前答案可行，找出最大的limit（可以二分）。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

简单的网络流,

我们把男生放到左边,女生放到右边,那么为了限制每个男生,应该给每个男生从源点连接一个流是 min ( n, n - bear[i] + m )的边。同样,每个女生,向汇点连流为 min ( n, n - bear[i] + m )的边。

对这个图做最大流(随便怎么做都可以,范围小的要死)。记录每次增广是从哪个男生进去的,从哪个女生出来的,分别给这两个人的ans[i] + 1。

最后,输出 min { ans }。

用一种时间复杂度极高的网络流:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 525ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

再用一个骗分程序(一初一牛创,23行):

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

拆点或者新建点都可以做

竟然没有秒杀

唉。。。地板了。。。等着题。。。