昨天有道题调了2h啊啊啊啊啊啊
最短路径
60+20+0，没有改
题解也完全看不懂，我好菜
强连通分量
15+7(100)+5->\color{green}100+100+100
\color{eedd00}T1
· 答案为最长链长度
· 那么有环怎么办呢
· 嗯今天是强连通分量那么就缩点吧
· 假如有个3点的环那么我们可以缩点成一个权值为3的点
· 拓扑排序快速求最长链
\color{green}T2
· 缩点+拓扑最长路模板
· 赛时洛谷调出来了
\color{red}T3
· 2-SAT.
· 如果x赛道变成有一种赛车不适用那是不是就好做了
· 暴力枚举，2^d
· 我们设$id{i\times2-1}为第一种适合的赛车，id{i\times2}为第二种适合的赛车(1\leq i\leq n)· 设需求为x,A,y,B，A’,B’为该赛道另一种可用的车，每一条边A→B代表如果A所在比赛使用A，那么B所在比赛使用B$
· 如果本来x比赛就不适合A，那我们啥事都不用干了
· 如果x比赛适合A，y比赛不适合B，那么连接A→A’，表示如果选了A一定无解
· 如果x比赛适合A，y比赛适合B，那么连接A→B,B’→A’，第二条边表示如果y选择B’，那么x不能选择A’
· 我们就可以愉快的缩点了！（这里有个雷）
· 缩点完如果任意比赛两种赛车在一个强连通分量内，那么此情况无解(毕竟有x比赛)
· 此时我们可以开始输出方案了
· 对于每一个比赛，如果第一种赛车的拓扑序比另一种赛车小，那么本场选第一种，否则选另一种
· 但是我们其实可以不用拓扑排序
· 由于Tarjan的性质，我们可以直接使用强连通分量编号！
· 然后雷就炸了 Tarjan核心代码如下↓
if(dfn[u]==low[u]){
int t;cnt++;
do{
t=s.top();che[t]=0;
s.pop();col[t]=cnt;
if(t==u){break;}
qz[u]+=qz[t];
}while(!s.empty());
st2[sc]=0;
}· 此处强连通分量必须使用cnt计数，否则强连通分量编号不是拓扑序