知识点总结

1. 状态图与同余最短路

• 将问题中的“状态”抽象为点，“操作”抽象为边，边权为操作代价，原问题转化为求最短路。
• 同余最短路选取最小面额 $A$ 为模数，用余数 $0\sim A-1$ 表示状态，转移为 $r \to (r+a_i)\bmod A$，边权为 $a_i$。
• 求出每个余数对应的最小可达数值后，答案即可由该最小值加上若干倍 $A$ 表示。

2. 0-1 BFS

• 针对边权仅为 0 或 1 的最短路问题，使用双端队列维护距离单调性。
• 松弛时，0 边更新的点放入队首，1 边更新的点放入队尾。
• 可保证队列中的距离始终单调不减，时间复杂度为 $O(|V|+|E|)$。

3. 差分约束

• 将不等式 $x_v – x_u \le w$ 转化为最短路中的边 $u \to v$（权 $w$）。
• 通过判断约束图是否存在负环来判定系统是否有可行解；无负环时，从源点出发的最短路值即为一组最大可行解。
• 区间和等约束可借助前缀和变量统一转化为差分形式。

4. 2-SAT

• 将每个析取子句 $(x_i=a)\lor(x_j=b)$ 转化为两个逆否的蕴含关系，并建出有向图。
• 用 Tarjan 求强连通分量，若某个变量的两个文字在同一 SCC 中则无解。
• 构造解时，选择 SCC 编号较小的文字（即拓扑序靠后）赋为真，满足所有蕴含关系。

5. Tarjan 离线 LCA

• 在 DFS 过程中，每访问完一个子节点，将其并查集合并到父节点上。
• 处理与当前节点 $u$ 相关的询问 $(u,v)$，若 $v$ 已访问过，则 $v$ 所在并查集的代表元即为 $LCA(u,v)$。
• 所有询问离线处理，总复杂度接近 $O((n+q)\alpha(n))$。

6. 欧拉通路、回路与构造

• 无向图欧拉回路要求所有非零度点连通且度数均为偶数；有向图要求忽略方向连通且入度等于出度（通路允许恰有一对出入度差 1 的点）。
• Hierholzer 算法通过 DFS 删边回溯构造回路；贪心选择当前最小未用出边可得到字典序最小的欧拉回路。
• BEST 定理用于计数有向欧拉回路数量，公式为 $\tau_s \prod_v (\text{outdeg}(v)-1)!$，其中 $\tau_s$ 为内向树数量。

7. 稀疏图环枚举

• 按度数排序后定向，确保每个点出度为 $O(\sqrt{m})$，总枚举量控制在 $O(m\sqrt{m})$。
• 三元环枚举：标记起点出邻点，枚举两条出边检查是否成环。
• 四元环分三类（两条二步路、三步链加弦、公共出邻点）分别统计，均基于二步路径枚举。
• 隐式图 BFS 中利用删除已访问邻边避免显式建出大量新增边。

8. 最小树形图（朱刘算法）

• 每次为所有非根点选择最小入边，若未成环则达到下界即为最优解。
• 若形成环，将环上所有点缩成一个超级点，并调整入边权值（减去原入边最小权），继续迭代。
• 最终方案需按缩点历史递归展开：外部边进入哪个子块，该子块就用这条边，其余子块沿用本轮记录的最小入边。

今日题目总结

C – Telephone Lines S

• 构建 $(k+1)$ 层分层图，第 $i$ 层表示已使用 $i$ 次免费机会（$0 \le i \le k$）。
• 同层节点间连原边权 $w$（代表付费边）；跨层节点间连边权 $0$（代表使用一次免费机会）。
• 从第 $0$ 层的节点 $1$ 出发跑 Dijkstra：同层松弛时取 $dis[v] = \max(dis[u], w)$，跨层（$0$ 权边）松弛时取 $dis[v] = dis[u]$。
• 最终答案为第 $k$ 层节点 $n$ 的 $dis$ 值（即最小化的最大付费边权），若该值为无穷大则输出 $-1$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,p,k,cnt,s=1,dis[500005],nxt[500005],val[500005],to[500005],head[500005],vis[500005];
void add(int u,int v,int w)
{
	to[++cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
struct node{
	int x,w;
	bool operator < (const node &b) const{
		return w>b.w;
	}
};
void dijkstra()
{
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=1;
	q.push({s,0});
	while(q.size())
	{
		int u=q.top().x;
		q.pop();
		if(vis[u])
		{
			continue;
		}
		vis[u]=1;
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(dis[v]>max(dis[u],val[i]))
			{
				dis[v]=max(dis[u],val[i]);
				q.push({v,dis[v]});
			}	
		}
	}
}
signed main(){
	scanf("%lld %lld %lld",&n,&p,&k);
	while(p--)
	{
		int x,y,z;
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
		for(int i=1;i<=k;++i)
		{
			add(i*n+x,i*n+y,z);
			add(i*n+y,i*n+x,z);
			add((i-1)*n+x,i*n+y,0);
			add((i-1)*n+y,i*n+x,0);
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=k;++j)
		{
			add((j-1)*n+i,j*n+i,0);
		}
	}
	dijkstra();
	if(dis[(k+1)*n]!=0x3f3f3f3f3f3f3f3f)
	{
		printf("%lld",dis[(k+1)*n]);
	}
	else
	{
		printf("-1");
	}
	return 0;
}

M – 加工零件

• 分别记录从 1 号点到每个节点的最短奇数长度路径和最短偶数长度路径（用数组 $odd$ 和 $even$），通过 BFS 按边数奇偶性分层更新。
• 对于查询 $(a, L)$，若 $L$ 为奇数且 $odd[a] \le L$，或 $L$ 为偶数且 $even[a] \le L$，则输出 Yes；否则输出 No。因为可以在任意边上来回走，使路径长度增加 $2$，所以只要存在对应奇偶性的最短路径不超过 $L$，就能恰好达到 $L$ 步。
• 若节点不可达，其对应距离为无穷大，则判断失败，输出 No。

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> e[100005];
int odd[100005],even[100005];
void bfs()
{
	memset(odd,0x3f,sizeof odd);
	memset(even,0x3f,sizeof even);
	queue<pair<int,int>> q;
	for(int i=0;i<e[1].size();++i)
	{
		odd[e[1][i]]=1;
		q.push({e[1][i],1});
	}
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		for(int i=0;i<e[x].size();++i)
		{
			if(y&1)
			{
				if(y+1<even[e[x][i]])
				{
					even[e[x][i]]=y+1;
					q.push({e[x][i],y+1});
				}
			}
			else
			{
				if(y+1<odd[e[x][i]])
				{
					odd[e[x][i]]=y+1;
					q.push({e[x][i],y+1});
				}
			}
		}
		q.pop();
	}
}
signed main(){
	int n,m,q;
	scanf("%lld %lld %lld",&n,&m,&q);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%lld %lld",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	bfs();
	while(q--)
	{
		int x,y;
		scanf("%lld %lld",&x,&y);
		if(y&1)
		{
			if(odd[x]>y)
			{
				printf("No\n");
			}
			else
			{
				printf("Yes\n");
			}
		}
		else
		{
			if(even[x]>y)
			{
				printf("No\n");
			}
			else
			{
				printf("Yes\n");
			}
		}
	}
	return 0;
}