acm模板byliyangWord格式文档下载.docx
《acm模板byliyangWord格式文档下载.docx》由会员分享，可在线阅读，更多相关《acm模板byliyangWord格式文档下载.docx（59页珍藏版）》请在冰点文库上搜索。
intnum[38][38];
voidZreo（）{
memset（num,0,sizeof（num））;
voiddig_One（）{
for（inti=1;
i<
=n;
i++）
num[i][i]=1;
};
intMod;
Matadd（MatA,MatB）{
Matans;
for（intj=1;
j<
j++）
ans.num[i][j]=（A.num[i][j]+B.num[i][j]）%Mod;
returnans;
Matmult（MatA,MatB）{
ans.Zreo（）;
for（intk=1;
k<
k++）{
ans.num[i][j]=（ans.num[i][j]+A.num[i][k]*B.num[k][j]）%Mod;
Matmy_pow（Matx,inty）{
ans.dig_One（）;
for（;
y;
y>
>
=1）{
if（y&
1）
ans=mult（ans,x）;
x=mult（x,x）;
MatA;
//全局变量
Matget_sum（intk）{//计算A+A^2+A^3+…..+A^K
if（k==1）
returnA;
elseif（k&
returnadd（get_sum（k-1）,my_pow（A,k））;
else{
MatB=get_sum（k>
1）;
returnadd（B,mult（B,my_pow（A,k>
1）））;
【KM二分最佳匹配】
constintsize=10008;
constintinf=100000000;
intgrid[size][size];
intlx[size],ly[size];
intn,m;
//n,m集合X，Y的元素个数
boolvisited_x[size],visited_y[size];
intmatch[size];
booldfs（intu）{
visited_x[u]=1;
for（intv=1;
v<
=m;
v++）{
if（!
visited_y[v]&
lx[u]+ly[v]==grid[u][v]）{
visited_y[v]=1;
if（match[v]==-1||dfs（match[v]））{
match[v]=u;
return1;
return0;
intKM（inttype）{//type=0最小权值匹配，type=1最大权值匹配
inti,j,k,sum=0;
if（type==0）{
for（i=1;
for（j=1;
grid[i][j]=-grid[i][j];
memset（ly,0,sizeof（ly））;
i++）{
lx[i]=-inf;
lx[i]=max（lx[i],grid[i][j]）;
memset（match,-1,sizeof（match））;
while
（1）{
memset（visited_x,0,sizeof（visited_x））;
memset（visited_y,0,sizeof（visited_y））;
if（dfs（k））
break;
intd=inf;
if（visited_x[i]）{
j++）{
visited_y[j]）
d=min（d,lx[i]+ly[j]-grid[i][j]）;
if（d==inf）
return-1;
if（visited_x[i]）
lx[i]-=d;
if（visited_y[i]）
ly[i]+=d;
if（match[i]!
=-1）
sum+=grid[match[i]][i];
returntype?
sum:
-sum;
【spfa（）差分约束系统】
//加入超级大原点
constintsize=1008;
structEdge{
intv;
intw;
intnext;
}edge[2*10008];
intvec[size],id,in_time[size],dist[size];
constintinf=INT_MAX;
inlinevoidadd_edge（intu,intv,intw）{
edge[id].v=v;
edge[id].w=w;
edge[id].next=vec[u];
vec[u]=id++;
voidinit（）{
memset（vec,-1,sizeof（vec））;
id=0;
memset（in_time,0,sizeof（in_time））;
boolin_que[size];
intspfa（ints）{
inti,j,u,v;
dist[i]=inf,in_que[i]=0;
dist[s]=0;
in_que[s]=1;
in_time[s]++;
queue<
int>
que;
que.push（s）;
while（!
que.empty（））{
u=que.front（）;
que.pop（）;
in_que[u]=0;
for（inte=vec[u];
e!
=-1;
e=edge[e].next）{
v=edge[e].v;
if（dist[v]>
dist[u]+edge[e].w）{
dist[v]=dist[u]+edge[e].w;
in_que[v]）{
in_que[v]=1;
in_time[v]++;
if（in_time[v]>
n）//必须>
que.push（v）;
returndist[n]==inf?
-2:
dist[n];
intmain（）{
inti,ml,md,a,b,w;
scanf（"
%d%d%d"
&
n,&
ml,&
md）;
init（）;
=ml;
a,&
b,&
w）;
add_edge（a,b,w）;
=md;
add_edge（b,a,-w）;
printf（"
%d\n"
spfa
（1））;
return0;
【tarjan算法缩点最长路】
usingnamespacestd;
constintsize=150010;
structEDGE{
}edge[size];
intid;
intvec[size],mystack[size],top;
intlow[size],dfn[size],idx,num;
boolinstack[size];
intbelong[size];
inlinevoidadd_edge（intu,intv）{
intsum[size];
ints,start;
voidtarjan（intu）{
low[u]=dfn[u]=idx++;
mystack[++top]=u;
instack[u]=1;
e!
=-1;
intv=edge[e].v;
if（dfn[v]==-1）{
tarjan（v）;
low[u]=min（low[u],low[v]）;
}
elseif（instack[v]）
low[u]=min（low[u],dfn[v]）;
if（low[u]==dfn[u]）{
num++;
do{
v=mystack[top--];
instack[v]=0;
belong[v]=num;
if（v==s）
start=num;
sum[num]++;
}while（v!
=u）;
idx=1;
top=-1;
num=0;
id=0;
memset（dfn,-1,sizeof（dfn））;
memset（instack,0,sizeof（instack））;
memset（sum,0,sizeof（sum））;
structNEWEDGE{
}new_edge[size];
intnew_link[size],new_id;
inlinevoidadd_new_edge（intu,intv）{
new_edge[new_id].v=v;
new_edge[new_id].next=new_link[u];
new_link[u]=new_id++;
intdist[size];
inti,j,m,u,v,cas=1;
while（scanf（"
m,&
s）!
=EOF）{
while（m--）{
%d%d"
u,&
v）;
if（u==v）
continue;
add_edge（u,v）;
if（dfn[i]==-1）
tarjan（i）;
dist[i]=0;
new_id=0;
memset（new_link,-1,sizeof（new_link））;
for（u=1;
u<
u++）{
if（belong[u]!
=belong[v]）{
add_new_edge（belong[u],belong[v]）;
intvisited[size];
memset（visited,0,sizeof（visited））;
que.push（start）;
dist[start]=sum[start];
visited[start]=1;
intans=dist[start];
visited[u]=0;
for（inte=new_link[u];
e=new_edge[e].next）{
v=new_edge[e].v;
if（dist[v]<
dist[u]+sum[v]）{
dist[v]=dist[u]+sum[v];
ans=max（ans,dist[v]）;
visited[v]）
Case%d:
\n"
cas++）;
ans）;
【二分图判定/黑白染色】
intv;
intnext;
}edge[2000010];
intcolor[1010];
intvec[1010];
intn,m,id,flag;
inlinevoidaddedge（intu,intv）{
edge[id].v=v;
edge[id].next=vec[u];
vec[u]=id;
id++;
voiddfs（intu,intcolor_type）{
color[u]=color_type;
intv=edge[e].v;
if（color[v]==0）
dfs（v,3-color_type）;
elseif（color[v]==color[u]）{
flag=0;
return;
intt,i,j,u,v,cas;
%d"
t）;
for（cas=1;
cas<
=t;
cas++）{
memset（color,0,sizeof（color））;
memset（vec,-1,sizeof（vec））;
flag=1;
m）;
v）;
addedge（u,v）;
addedge（v,u）;
if（color[i]==0）{
dfs（i,1）;
}}
if（flag）
Yes\n"
）;
}
【二分最大匹配】
constintsize=508;
structNode{
intleft;
intright;
}girl[size];
intboy[size];
intgirl_n,boy_m;
boolgrid[size][size];
boolvisited[size];
intmatch[size],cx[size];
intdfs（intu）{
=boy_m;
if（grid[u][v]&
!
visited[v]）{
visited[v]=1;
cx[u]=v;
return1;
intmax_match（）{
intans=0;
memset（cx,-1,sizeof（cx））;
=girl_n;
if（cx[i]==-1）{
ans+=dfs（i）;
inti,j,x,y;
girl_n,&
boy_m）!
x,&
y）;
if（x>
y）
swap（x,y）;
girl[i].left=x;
girl[i].right=y;
boy[i]）;
memset（grid,0,sizeof（grid））;
if（girl[i].left<
=boy[j]&
boy[j]<
=girl[i].right）
grid[i][j]=1;
max_match（））;
【map[string,string]手写】
structnode{
charname[25];
charfun[85];
friendbooloperator<
（constnode&
a,constnode&
b）{
returnstrcmp（a.name,b.name）<
0;
}names[N];
intk;
intfind_name（char*name）{
intleft=0,right=k-1,mid;
while（left<
=right）{
mid=（left+right）>
1;
if（strcmp（names[mid].name,name）==0）
returnmid;
elseif（strcmp（names[mid].name,name）>
0）
right=mid-1;
elseif（strcmp（names[mid].name,name）<
left=mid+1;
return-1;
【double二分】注意eps的选择
constintsize=108;
constdoubletwo_PI=2.0*acos（-1.0）;
doubledist[size];
doubleradian（doublea,doubleb,doublec）{
returnacos（（a*a+b*b-c*c）/（2.0*a*b））;
doubleSUM_AGE（doublec）{
doublesum=0.0;
for（inti=0;
n;
sum+=radian（dist[i],dist[i+1],c）;
returnsum;
constdoubleeps=1e-8;
intt,i,j;
doubleleft,right,mid,ans;
//0printf（"
%.10lf"
eps）;
t）;
for（intcas=1;
n）;
for（i=0;
%lf"
dist[i]）;
dist[n]=dist[0];
right=1000000000.0;
left=0.0;
right=min（dist[i]+dist[i+1],right）;
left=max（fabs（dist[i]-dist[i+1]）,left）;
ans=0;
while（right-left>
eps）{
mid=（left+right）/2.0;
if（fabs（SUM_AGE（mid）-two_PI）<
ans=mid;
elseif（SUM_AGE（mid）>
two_PI）
right=mid;
else
left=mid;
"
cas）;
if（fabs（SUM_AGE（ans）-two_PI）<
eps）
%.3lf\n"
impossible\n"
）;
doubleside[108];
doublePI=3.141592654;
inlinedoubleMax（doublex,doubley）{
returnx>
y?
x:
y;
doublejudge（doubler）{
doublelen=2.0*r*sin（PI/n）;
inti;
if（side[i]+side[i+1]<
len）
return4.0*PI;
doubletemp=（side[i]*side[i]+side[i+1]*side[i+1]-le
升级会员 