首页 > 代码库 > [TD Cup 2014] TDL的YC牌 & TDL的幼儿园
[TD Cup 2014] TDL的YC牌 & TDL的幼儿园
TDL的YC牌
传说中的置换群？反正不懂。我的思路竟然是对的，可是为何只有20分？
（1）尼玛每行数据输出后回车不打！
（2）写gcd函数脑残把a mod b写成a-b，大大减慢速度…
（3）看标程才想到用快速幂，第一次知道置换也可以快速幂。
（4）大小姐啊麻烦你下次看数据范围别把0的个数给数错的……
果然什么题都要见识一下。跑数据的时候速度仍然堪忧（最后三个点），可能是电脑问题，也可能还能优化？
program yc;const maxn=100000+10; q=1e-6;var t1,t2,t3,jn,p:int64; tt3:real; a,b,c,d,base,baset,ans,anst:array[1..maxn] of longint; i,t,n,jt,x,k,j:longint;function gcd(a,b:int64):integer;var t:int64;begin if b>a then begin t:=a;a:=b;b:=t; end; if (a=0) or (b=0) then exit(1); if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);end;function eq(a:real;b:int64):boolean;begin if abs(a-b)<=q then exit(true) else exit(false);end;begin assign(input,‘yc10.in‘);reset(input); assign(output,‘yc10.out‘);rewrite(output); readln(t); for i:=1 to t do begin readln(n,t1,t2); jn:=1; for j:=1 to n do read(b[j]); for j:=1 to n do begin jt:=1;x:=b[j]; while x<>j do begin x:=b[x]; inc(jt); end; jn:=jn div gcd(jn,jt) * jt; end; {for j:=1 to n do a[j]:=j; fillchar(jp,sizeof(jp),$7f); c:=a; for j:=1 to 30 do begin for k:=1 to n do d[k]:=c[b[k]]; c:=d; for k:=1 to n do if (a[k]=d[k]) and (k<jp[k]) then jp[k]:=j; end;} {for j:=1 to n do jn:=jn*jt div gcd(jn,jt); } for k:=-t2 to t2 do begin tt3:=(t1+k*jn)/t2; if (eq(tt3,round(tt3))) and (tt3>0) then break; end; t3:=round(tt3); for j:=1 to n do a[j]:=j; for j:=1 to n do ans[j]:=j; for j:=1 to n do anst[j]:=j; for j:=1 to n do base[j]:=b[j]; p:=t3; while p>0 do //for p:=1 to t3 do begin {for k:=1 to n do begin //c[k]:=b[a[k]]; c[b[k]]:=a[k]; end; a:=c; inc(p);} if p mod 2=1 then for j:=1 to n do anst[j]:=ans[base[j]]; ans:=anst; for j:=1 to n do baset[j]:=base[base[j]]; base:=baset; p:=p div 2; end; {for j:=1 to n do c[a[j]]:=j;} for j:=1 to n do write(ans[j],‘ ‘); writeln; end; close(input);close(output);end.
TDL的幼儿园
昨天又4个人AC，果然我是弱渣，根本看不出这是网络流模型- -！今天学习了Dinic算法，为何感觉比之前写的更简短且容易理解？（咳咳之前那次写的手工栈）
对题目进行网络流建模，源点（编号0）向每个小朋友连一条边，容量为Ci，所有糖向汇点（编号m+n+1）连一条边，容量为Vi，小朋友和它想要的糖之间连一条容量为inf的边。（要注意inf最好不要设置成maxlongint，否则万一它的flow为负，两者一加就超过范围了，结果坑爹的Lazarus还不报错，传进去一个接近-maxlongint的值，当然这有可能是初始化一开始出错造成的。最后我inf设置成了maxlongint div 2）
P.S. 题解要不要写的那么暴力啊，一会儿割小朋友，一会儿把它的所有的糖给割掉…
跟踪了一些变量来搞懂，没有时间把它搞精通了，所以默默地背代码去了。
话说，我100年没有写链表了！…貌似，这次写的还比较顺…
程序很大程度参考了http://www.cnblogs.com/htfy/archive/2012/02/15/2353147.html，我没有用静态链表，所以没写xor 1这种办法，用了dec_flow这样一个查找+修改flow的过程。
一开始跑数据死循环啊！尼玛建边的时候下次注意一点，这次建双向边但是回边的flow是0，不能和去边一样啊 =v=
program kd2;type ptype=^node; node=record w,v,flow:longint; next:ptype; end;const inf=maxlongint div 2; maxn=1000;var n,m,tar,sta,v,c,x,cn,i,j:longint; head:array[0..2*maxn+10] of ptype; visit:array[0..2*maxn+10] of boolean; d,q:array[0..2*maxn+10] of longint;// distance to st;function min(a,b:longint):longint;begin if a<b then exit(a) else exit(b);end;procedure add_edge(st,ed,w:longint);var p,q,pre:ptype;begin new(q); q:=head[st]; new(p); p^.w:=w;p^.v:=ed;p^.flow:=0;p^.next:=nil; if q=nil then begin new(head[st]); head[st]^:=p^; end else begin while q<>nil do begin pre:=q; q:=q^.next; end; new(q); q^:=p^; pre^.next:=q; end;end;function bfs:boolean;var star,rear,x,u:longint; y:ptype;begin fillchar(visit,sizeof(visit),false); fillchar(q,sizeof(q),0); star:=1;rear:=1;d[sta]:=1;visit[sta]:=true;q[star]:=sta; while star<=rear do begin x:=q[star]; y:=head[x]; while y<>nil do begin if (not visit[y^.v]) and (y^.flow<y^.w) then begin visit[y^.v]:=true; d[y^.v]:=d[x]+1; inc(rear); q[rear]:=y^.v; end; y:=y^.next; end; inc(star); end; exit(visit[tar]);end;procedure dec_flow(st,ed,delta:longint);var x:ptype;begin x:=head[st]; while x^.v<>ed do x:=x^.next; x^.flow:=x^.flow-delta;end;function add_flow(p,maxflow:longint):longint;var u,o:longint; y:ptype;begin if (p=tar) or (maxflow=0) then exit(maxflow); add_flow:=0; y:=head[p]; while y<>nil do begin if (d[y^.v]=d[p]+1) and (y^.flow<y^.w) then begin o:=add_flow(y^.v,min(maxflow,y^.w-y^.flow)); if o>0 then begin inc(y^.flow,o); //dec(op_y.flow,o); dec_flow(y^.v,p,o); dec(maxflow,o);inc(add_flow,o); if maxflow=0 then break; end; end; y:=y^.next; end;end;function network:longint;begin network:=0; while bfs do begin inc(network,add_flow(sta,inf)); end;end;begin assign(input,‘kd.in‘);reset(input); assign(output,‘kd.out‘);rewrite(output); readln(n,m);sta:=0;tar:=m+n+1; for i:=1 to m do begin read(v); add_edge(n+i,tar,v); add_edge(tar,n+i,0); end; for i:=1 to n do begin read(c); cn:=cn+c; add_edge(sta,i,c); add_edge(i,sta,0); read(x); for j:=1 to x do begin read(c); add_edge(i,n+c,inf); add_edge(n+c,i,0); end; readln; end; writeln(cn-network);end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。