T1

problem

给出一张n个点,m条边的又向带权图.要求找一条从1到n且边权递增的最短路.

ans

设disi表示1到i号边权递增的最短路长度.把边从小到大排序,每次加入一条边(u,v,w),考察dis(u)是否已经存在一个有意义的值,如果可用则用dis(u)+w去更新dis(v).

T2

problem

给出一个N个点的无向图,其中1是首都.现在有两种边:m条道路,每条链接两个节点.k条铁路,每条链接首都和另外一个点.边有边权.问删去多少条铁路可以使得首都到所有点最短路都不变.

ans

T3

problem

给定一个N个点M条边的无向图.定义d(i,j)表示两点间的最短路.每个点定义了点权ai.现在对于图中每个点,你都需要计算:
$$
min_{j=1}^{n}(2\times d(i,j)+a_j)
$$

ans

由于数据范围巨大,我们只能跑一遍最短路.因此每个i只能作为汇点(终点).所以我们建立一个超级原点向所有点建立边权为ai的边,跑一边最短路,通过这种操作,我们就可以直接求出d(i).而题目中的式子可以转化成:
$$
f[i]=min_{j=1}^{n}(d(0,j)+d(j,i))=d(i)\text{(边权已变成二倍)}
$$
所以这道题就做完了

T4

problem

给出一张n个点,m条边的无向带权图.其中有k个关键点.求这k个关键点两两之间最短路的最小值.

ans

首先我们引入一个经典模型,如果要求图上连接两个点集的最短路,我们只需要建立一个超级源,向其中一个集合所有点链接边权为0的边然后跑最短路.那么在这个题中,我们要通过将K个关键点两两之间都至少一次分到两个集合中,来求出最小值.

那么怎么分组呢?我们考虑k个关键点的标号的二进制中至少有一位不同.所以按照二进制位来分组.

T

problem

给出一张$n\times m$的网格图,其中每个点可能是障碍,空地,A的基地,B的基地,C的基地.现在ABC随机选一个基地作为起点,然后他们会选择一个空地会合,选择的这个点必然是他们三个人前往的距离总和最小的点.

求这个距离总和的期望大小(AB基地的总数<=50)

ans

T6

problem

有一张图,每条边的边权分别是关于时间的不同的二次函数.求最小生成树.假设没有负权边.

ans

T7

problem

问1-N中所有数转化为二进制数之后1的个数之积.

ans

令f[i][j][k]表示现在在第i位,数位中有j个1,跟上界之间的大小关系K.如果第i位取0,$f[i-1][j][k]\Rightarrow f[i][j][k|N(i)]$.如果第i位取1,那么$f[i-1][j][k]\times max(k,N(i))\Rightarrow f[i][j+1][k]$

T8

problem

——Gensokyo