作业帮四川oi的某道题洪水洪水flood.exe乡下有n(n
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/05 17:22:09
四川oi的某道题洪水洪水flood.exe乡下有n(n
四川oi的某道题洪水
洪水
flood.exe
乡下有n(n
四川oi的某道题洪水洪水flood.exe乡下有n(n
用的是比较囧的算法.虽然是阶乘级,但是n很小可以过.
我是用的用并查集（用其中字典序最小的元素做代表元）+HASH表存状态,还要加一个双映射,枚举每条边做转移.
考试时hash表时一个用的是and,一个是用的mod,结果wa7个点.
program xqz;
const mo=maxint; maxn=800000;
type arr=array[0..8] of longint;
var
i,j,k,m,n,now,r,tot,f1,f2,aim,s,t,e:longint;
q:array[0..1,0..maxn] of arr;
f:array[0..1,0..maxn] of real;
last,next,hash,pos,p1:array[0..maxn+mo] of longint;
ss,tt:array[0..30] of longint;
p:array[0..30] of real;
a,ci:arr;
yes,ok:boolean;
ans:extended;
function get(a:arr):longint;
var now,i:longint;
begin
now:=0;
for i:=1 to n do
inc(now,(a[i]-1)*ci[i-1]);
get:=now;
end;
procedure insert(now:longint;lv:extended);
var k:longint;
begin
k:=now and mo;
while next[k]0 do
begin
k:=next[k];
if hash[k]=now then
begin
f[t,p1[k]]:=f[t,p1[k]]+lv;
exit;
end;
end;
inc(e); hash[e]:=now; next[k]:=e; last[e]:=k;
inc(r); q[t,r]:=a; //!
f[t,r]:=lv; pos[r]:=e; p1[e]:=r;
end;
begin
assign(input,'flood.in'); reset(input); assign(output,'flood.out'); rewrite(output);
read(n,m);
for i:=1 to m do read(ss[i],tt[i],p[i]);
ci[0]:=1; for i:=1 to n do ci[i]:=ci[i-1]*n;
s:=1; t:=0; for i:=1 to n do a[i]:=i;
r:=0; e:=mo; now:=get(a); insert(now,1); next[now and mo]:=0;
for i:=1 to m do
begin
s:=(s+1) and 1; t:=(t+1) and 1; e:=mo; tot:=r; r:=0;
for j:=1 to tot do
begin
a:=q[s,j]; f1:=a[ss[i]]; f2:=a[tt[i]];
now:=get(a);
insert(now,f[s,j]*p[i]);
if f1