编译通过...

├ 测试数据 01：答案错误...

　├ Hint: lolanv好可爱哦..　├ 标准行输出

　├ 错误行输出

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

　├ 错误行输出

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

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

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

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

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

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

Unaccepted 有效得分：70 有效耗时：181ms

匈牙利算法指导思想...为何...

测试数据1：标准答案900，错误答案899

测试数据2：标准答案691，错误答案689

..........................暂且当作分割线............................

编译通过...

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

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

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

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

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

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

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

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

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

果然...只具有思想是没有普遍性的...

还是百度好.

编译通过...

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

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

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

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

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

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

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

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

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

数据几乎全是实型的，千万注意，我wa了3遍==

二分图最大匹配……

由于不喜欢匈牙利算法……

直接上最大流……

但是朴素的BFS增广鬼死很惨……

于是改用Dinic

就是在增广前预处理出距离标号

找增广鬼的时候要求dist[v]+1=dist[j]

不会写匈牙利。。。直接写了个网络流。。。

建超级源S，超级汇T。从T到每一个人连一条流量为1的边，从每个传送点到会连一条流量为1的边，如果一个人可以到一个传送点，就在这两个点之间连一条流量为一的边，然后做个最大流即可。。。。

匈牙利算法的简单讲解http://plfxy.blog.hexun.com/27520783_d.html

答案正确... 9ms

第一个点的耗时（最大的）

匈牙利算法硬搞即可 配合边表

二分图的最大匹配就是加一个super source和super sink 然后网络流

不过理论复杂度达到三方 实际复杂度比匈牙利差 所以不大多人用

编译通过...

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

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

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

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

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

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

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

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

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

ms我的还是比较快。第二遍写匈牙利算法，一次AC。久违的AC啊！

这道题是求二分图的最大匹配，最基础的匈牙利算法，不会的可以去学一下。预处理时，凡是可以小衫到达的传送点，之间就加一条边，然后就是把匈牙利算法默写上去了。

二分图的最大匹配ms还能用网络流解，可惜我不会……

慎用READLN

不然10分

先是用整型读的实型

后又将匈牙利算法中的边的有向性编成了无向

提交了n次

顶歇！！！

编译通过...

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

写了个匈牙利，一次AC！

#include

#include

#include

int r,a;

double t;

int match[1001];

char flag[1001],map[1001][1001];

struct jy{

double x;

double y;

}door[1001];

struct jj{

double x;

double y;

double v;

}shan[1001];

double dis(double x1,double y1,double x2,double y2){

return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

int search(int x){

int i,temp;

for (i=1;i

那个叫man75319的,BS你.

不要拿百度百科上的当你自己的...

另外此题和二分图最大匹配有呵关系?

毕竟难度是1啊...

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

呀呀呀,的确是最大匹配,差点没看出来...

rp...

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

总算秒杀了...

program Project1;

const lam=1e-10;

var x,y:array[1..1000]of real;

g:array[1..1000,1..1000]of boolean;

match:array[1..1000]of integer;

vis:array[1..1000]of boolean;

r,a,t,s,i,j:integer;

x1,y1,v:real;

function dfs(i:integer):boolean;

var j:integer;

begin

for j:=1 to a do

if gand not vis[j]

then begin

vis[j]:=true;

if(match[j]=0)or dfs(match[j])

then begin

match[j]:=i;

exit(true);

end;

end;

exit(false);

end;

begin

readln(r,a,t);

fillchar(x,sizeof(x),0);

fillchar(y,sizeof(y),0);

fillchar(g,sizeof(g),0);

fillchar(match,sizeof(match),0);

for i:=1 to a do

read(x[i],y[i]);

for i:=1 to r do

begin

readln(x1,y1,v);

for j:=1 to a do

if sqr(x[j]-x1)+sqr(y[j]-y1)-sqr(v*t)

一个错误的匈牙利(只求极大匹配)都能55分,还好最后是AC了

为什么啊

为什么我好几个点输出0

。。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

为什么会第一个点......

我真傻，真的。

打字错误是天下最×的错误。

第一次，第j个小杉的速度，我打成了v[i]，应该是v[j]，居然10分！

第二次，时间每次取最小值，居然打成了 max，居然也10分！！

无语，RP……！！！

标准匈牙利

用网络流和马甲刷了n次后，终于...

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

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

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

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

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

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

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

通过了

怎样做到0秒?

我的才18......

无效数字格式？？？？？？

怎麽回事？？

大家看一下！！！！！

匈牙利算法

求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。

增广路的定义(也称增广轨或交错轨)：

若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

由增广路的定义可以推出下述三个结论：

1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

2－P经过取反操作可以得到一个更大的匹配M’。

3－M为G的最大匹配当且仅当不存在相对于M的增广路径。

用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)

算法轮廓：

(1)置M为空

(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M

(3)重复(2)操作直到找不出增广路径为止