92 条题解
-
1
zwz LV 7 @ 3 年前
清爽(丑陋)的代码
-
15 年前@
匈牙利算法,题目输入注意(因为顺序不对错交n次QAQ),第一行m,n,t,之后是n行,再m行。
-
17 年前@
1开始j打成i了,郁闷
-
17 年前@
-
08 年前@
测试数据 #0: Accepted, time = 78 ms, mem = 3028 KiB, score = 15
测试数据 #1: Accepted, time = 62 ms, mem = 1480 KiB, score = 15
测试数据 #2: Accepted, time = 31 ms, mem = 1096 KiB, score = 15
测试数据 #3: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1092 KiB, score = 15
测试数据 #5: Accepted, time = 15 ms, mem = 1088 KiB, score = 15
测试数据 #6: Accepted, time = 31 ms, mem = 1092 KiB, score = 15
Accepted, time = 232 ms, mem = 3028 KiB, score = 100最开始两次莫名其妙的越界。。明明是1010都不行吗 变成10010就AC了。。
裸的二分图匹配 这里用网络流解了 -
08 年前@
第一次---10分--难过
于是来翻了翻题解,看着吐槽,我笑着笑着就忘了我的代码哪错了——于是我又把那份代码提交了(哦不)
最后,再次翻阅题解,
改掉了:
x,y,t是实数型,要用float -
09 年前@
怕精度问题就不要开方啊。。。雪崩
-
09 年前@
P1212Way Selection
Accepted记录信息
评测状态 Accepted
题目 P1212 Way Selection
递交时间 2015-07-08 22:02:36
代码语言 C++
评测机 VijosEx
消耗时间 91 ms
消耗内存 4236 KiB
评测时间 2015-07-08 22:02:43评测结果
编译成功
测试数据 #0: Accepted, time = 46 ms, mem = 4236 KiB, score = 15
测试数据 #1: Accepted, time = 15 ms, mem = 4236 KiB, score = 15
测试数据 #2: Accepted, time = 15 ms, mem = 4236 KiB, score = 15
测试数据 #3: Accepted, time = 0 ms, mem = 4236 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4232 KiB, score = 15
测试数据 #5: Accepted, time = 0 ms, mem = 4232 KiB, score = 15
测试数据 #6: Accepted, time = 15 ms, mem = 4232 KiB, score = 15
Accepted, time = 91 ms, mem = 4236 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>using namespace std;
int r , a , t;
float x[1000 + 2];
float y[1000 + 2];
float x1d[1000 + 2];
float y1d[1000 + 2];
float v[1000 + 2];
int use[1000 + 2];
int graph[1000 + 2][1000 + 2];
int match[1000 + 2];
int ans;
int i , j;bool hungary( int x )
{
int i;
for( i = 1 ; i <= a ; i++ )
if( graph[x][i] && !use[i] )
{
use[i] = 1;
if( !match[i] || hungary( match[i] ) )
{
match[i] = x;
return 1;
}
}
return 0;
}int main()
{
scanf( "%d %d %d" , &r , &a , &t );
for( i = 1 ; i <= a ; i++ )
scanf( "%f %f" , &x[i] , &y[i] );
for( i = 1 ; i <= r ; i++ )
scanf( "%f %f %f" , &x1d[i] , &y1d[i] , &v[i] );
for( i = 1 ; i <= a ; i++ )
for( j = 1 ; j <= r ; j++ )
if( sqrt( ( x1d[j] - x[i] ) * ( x1d[j] - x[i] ) + ( y1d[j] - y[i] ) * ( y1d[j] - y[i] ) ) - v[j] * t <= 0 )
graph[j][i] = 1;
for( i = 1 ; i <= r ; i++ )
{
memset( use , 0 , sizeof( use ) );
if( hungary( i ) )
ans++;
}
cout << ans << endl;
return 0;
}
读入。。。 -
010 年前@
读入一定要用“read”,血的教训。
-
010 年前@
把j打成i还查了好几次,晕==||
-
012 年前@
每次看题解到一半就会无奈地放弃……太长了。总结一下,看看你有没有出现以下错误,没有的话,往下看大牛们的吧。
[首先说明,此题正解是二分图的最大匹配,使用匈牙利算法或者网络流]
1、i,j写反[请不要笑,下面有位神牛笑了别人结果rp--自己也写反了]
2、精度问题,据说判断要用速度*时间>=距离判断[往下找你可以看到红字部分]
3、知道为什么有精度问题吗?因为数据中t和坐标是实数,real和double都可以
4、读入问题……用read不要用readln。不然WA10,看题目"第二行有a对实数,第i对数表示第i个传送点的坐标,这些坐标绝对值均不超过1e6"
5、还是读入问题,写数据规模的人很不厚道,读入是r,a,t,数据规模是' -
015 年前@
Accepted 有效得分:100 有效耗时:0ms
典型的匈牙利算法~~
-
015 年前@
是不是题目没说清楚啊,输入问题!
readln-->real wa 了n次 -
015 年前@
...匈牙利的判重位置写错了。。。囧rz。
-
015 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
距离比较时,将>=打成了>,结果85,害我wa了一次 -
015 年前@
编译通过...
├ 测试数据 01:答案正确... 338ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:338msprogram p1212;
var a:array[1..1000,1..1000] of boolean;
x,y:array[1..1000] of real;
link:array[1..1000] of integer;
v:array[1..1000] of boolean;
i,j,k,l,m,n,ans,p,q,r:integer;
c,d,w:real;
function find(x:integer):boolean;
var g:integer;
begin
for g:=1 to m do
if a[x,g] and not v[g]
then begin v[g]:=true;
if (link[g]=0) or (find(link[g]))
then begin link[g]:=x;exit(true);end;
end;
exit(false);
end;
begin
read(m,n,k);
for i:=1 to n do read(x[i],y[i]);
for i:=1 to m do begin
read(c,d,w);
for j:=1 to n do
begin
if sqrt(sqr(x[j]-c)+sqr(y[j]-d)) -
015 年前@
readln -> 10 分
read -> AC -
015 年前@
题目骗我说多组数据啊。。
写了个while not eof do。
卡了两台评测机。
后来6k评超时。再交碰上Smdcn就AC了- - -
015 年前@
赤裸裸的二分图最大匹配。。。但是本菜不会……
-
015 年前@
85分AC...