以前的题
CF1515F Phoenix and Earthquake
给定一张 \(n\) 个点 \(m\) 条边的无向连通图和正整数 \(x\) ，每个点有非负点权 \(w_i\) 。如果一条边 \((u,v)\) 满足 \(w_u+w_v>x\) 则可以将这两个点缩起来，新点的点权为 \(w_u+w_v-x\) 。判断这张图能否缩成一个点，如果可以还需输出每次缩的是哪条边。
\(2\le n,m\le 3\times10^5\) 。
先摆出结论：如果 \(\sum_{i=1}^{n}w_i\;<(n-1)\times x\) 则无解，考虑归纳证明。在 \(n\) 个点的树中，对于叶子节点 \(u\) ，若 \(w_u\ge x\) ，那我们直接将 \(u\) 和 \(fa_u\) 缩起来，变成一个 \(n-1\) 个点的树，此时仍满足条件。否则若 \(w_u<x\) ，我们直接删掉点 \(u\) 和连向 \(fa_u\) 的边，大数减小数大于小数减大数，所以剩下的 \(n-1\) 个点的树仍满足条件，我们只需要最后缩点 \(u\) 即可。此时做法已经很显然了，搞出来这个图的一颗生成树， \(dfs\) 一遍，\(w_u\ge x\) 的点加入答案队列中，然后将权值修改，否则将其加入答案栈中，最后先输出队列后输出栈内的边即可。时间复杂度 \(O(n)\) 。
CF1517D Explorer Space
给定一个四联通的 \(n\times m\) 的带边权网格图，对于每个节点求恰好 \(k\) 步回到自身的最短路径，若无法到达输出 \(-1\) 。
\(1\le n,m\le 500\) ，\(k\le 20\) 。
发现只有当 \(k\) 是奇数的时候才无解，所以 \(k\) 为偶数的时候就转化成走 \(\frac{k}{2}\) 步，且走出去和走回来的路径可以相同，所以最终转化为走 \(\frac{k}{2}\) 步的最小权值。很明显可以直接 \(dp\) ，设 \(f_{i,j,k}\) 表示当前在点 \((i,j)\) 走了 \(k\) 步的最小权值。转移对于每个节点 \((i,j)\) 枚举其四联通的节点转移过来即可。时间复杂度为 \(O(nmk)\) 。
洛谷P4320 道路相遇
给定 \(n\) 个点 \(m\) 条边的无向连通图。\(Q\) 次询问两点之间的必经点数量（包括出发点和终点）。
\(n\le 5\times 10^5\) ，\(Q\le 5\times 10^5\) ，\(m\le \min(\frac{n(n-1)}{2},10^6)\) 。
容易发现两点间的必经点个数就是路径上割点的个数。所以我们直接建圆方树，发现就是求两点间路径上圆点的数量，由于圆方树上路径是圆点和方点间隔分布，所以答案就是两点间路径长度除以二加一，直接对圆方树做树剖即可。时间复杂度为 \(O(n\log n+m+Q\log n)\) 。
CF1051F The Shortest Statement
给定 \(n\) 个点 \(m\) 条边的带边权无向图，满足 \(m-n\le 20\) ，\(Q\) 次询问两点间的最短路径。
\(n,m\le 10^5\) ，\(Q\le 10^5\) 。
由于 \(m-n\le 20\) 的性质，我们容易发现给出的无向图可以拆成一棵生成树和单独的 \(20\) 多条边，所以两点间最短路径可以分为两种，一是只在最小生成树上的，二是包含非最小生成树上的边。对于一，我们对最小生成树做树剖将两点间路径拆成与 \(lca\) 有关的形式即可，对于二，我们记录下非最小生成树上的边，对于这些边的左右端点，我们以它们为起点跑单源最短路径即可。时间复杂度为 \((m-n+1)\log n+n\log n+Q\log n\) 。
CF732F Tourist Reform
给定一个 \(n\) 个点 \(m\) 条边的无向连通图，要求将所有边定向，设 \(f_i\) 表示点 \(i\) 可以到达的点的数量，最大化 \(\min \limits_{i=1}^{n}{f_i}\) ，输出最大值和每条边的方向。
\(n,m\le 4\times 10^5\) 。
我们容易发现，对于一个边双连通分量，一定存在一种定向方案使得其中任意两个节点能够互达，即它们的 \(f\) 值为这个边双的大小。所以我们对原图进行边双缩点，这样会得到一棵树，每条边就对应原图的一个桥。现在我们单独来看树的情况，假设它有 \(n\) 个点，因为它有 \(n-1\) 条边，那么定向后它的出度之和最大为 \(n-1\) ，所以一定存在某个点它的出度是 \(0\) ，也就是说这个点的 \(f\) 值为 \(0\) 。回到原题上来，也就是一定有某个边双，其内部的点的 \(f\) 值就是这个边双的大小。那么最大值就是所有边双的大小的最大值了。对于输出方案，我们从大小最大的那个边双里的一个点直接 \(dfs\) 即可。时间复杂度为 \(O(n+m)\) 。
技巧：找二分图中可以不在最大匹配上的点，在跑完最大流后可以进行如下操作：
void get(int u,int x)
{
if(vis[u]) return;
vis[u]=true;
if(belong[u]==x) flag=true,res[u]=true;
//belong是这个点的类型，左部点为1，右部点为0
//res表示这个点能否不在最大匹配上
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(edge[i].w==x) get(v,x);
}
}
int main()
{
//用最大流求二分图最大匹配
get(s,1);
memset(vis,0,sizeof(vis));
get(t,0);
}
11.5 讲课
洛谷P4366 [Code+#4] 最短路
考虑优化第一部分的完全图建图。假如我们要从 \(1\) 走到 \(7\) ，如果直接走，代价是 \(6C\) 。而如果我们按位去走，先从 \(1\) 走到 \(3\) ，代价为 \(2C\) ，再从 \(3\) 走到 \(7\) ，代价为 \(4C\) ，总的代价仍然是 \(6C\) 。这其实启发我们完全可以只保留只变化一个二进制位的边，这样总代价是不会变化的，那么就只需要保留从 \(x\) 连向 \(x\bigoplus2^k\) 的边，但要满足 \(x\bigoplus2^k\le n\) 。而如果点的编号出现了 \(0\) 该怎么办呢，事实上 \(0\) 不会影响答案，因为 \((u\bigoplus 0)+(0\bigoplus v)=u+v\ge u\bigoplus v\) 。这样整张图的边数就降到了 \(O(n\log n+m)\) 级别，然后再用 dij 跑最短路即可。
洛谷P2505 [HAOI2012] 道路
以前做过。
gym104197D/QOJ5520 Distance Parities
如果有解，那么直接将距离为奇数的两个点之间连一条边也一定是合法的。考虑在某组合法解中两个点 \(u,v\) 之间的距离为偶数 \(2k\) ，那么在这两个点的最短路上一定存在一个点 \(p\) ，使得 \(u\) 到 \(p\) 的距离为 \(1\) ，\(p\) 到 \(v\) 的距离为 \(2k-1\) ，也是奇数。而按照我们的做法，我们一定会连一条从 \(u\) 到 \(p\) 和从 \(p\) 到 \(v\) 的边，此时新图中 \(u\) 到 \(v\) 的距离为 \(2\) ，仍然是偶数。因此我们只需要建完图后跑一遍 floyd 判断两点间距离是否满足给出的奇偶性，以及是否是连通图即可。
int T,n,dis[N][N];
char c[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dis[i][j]=INF;
for(int i=1;i<=n;i++) dis[i][i]=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>c[i][j];
if(c[i][j]=='1') dis[i][j]=1,++cnt;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && i!=k && j!=k)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
bool flag=true;
for(int i=1;i<=n && flag;i++)
for(int j=1;j<=n && flag;j++)
if(dis[i][j]%2!=c[i][j]-'0' || dis[i][j]==INF) flag=false;
if(flag==false) cout<<"NO"<<'\n';
else
{
cout<<"YES"<<'\n'<<cnt/2<<'\n';
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(c[i][j]=='1') cout<<i<<" "<<j<<'\n';
}
}
return 0;
}
gym104023F Mooncake Delivery
不妨考虑答案的形态，由于我们每走到一个点就可以回收其它颜色的所有顶点的点权，那么我们要将路径按照颜色去分段，那么初始需要的点权就是每一段的点权和加上下一段的起始点的点权的最大值。于是我们先按照每种颜色将图分成几个同色连通块，每块内部用 floyd 求出两两之间最短路。然后就可以考虑枚举每一段的起点 \(u\) ，终点 \(v\) 和下一段的起始点 \(w\) ，连边 \((u,w,dis_{u,v}+val_w)\) ，建出一张新的有向图。然后在这张新图上跑一个边权取 \(\max\) 的 floyd 即可。
int n,m,col[N],val[N];
ll dis[N][N],dis2[N][N],ans[N][N];
bool vis[N][N];
int main()
{
int T=read();
while(T--)
{
n=read(),m=read();
for(int i=1;i<=n;i++) col[i]=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dis[i][j]=dis2[i][j]=INF;
for(int i=1;i<=n;i++) dis[i][i]=val[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) vis[i][j]=false;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
vis[u][v]=vis[v][u]=true;
dis[u][v]=dis[v][u]=val[u]+val[v];
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
if(i==k || col[i]!=col[k]) continue;
for(int j=1;j<=n;j++)
{
if(j==k || i==j || col[i]!=col[j] || col[j]!=col[k]) continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]-val[k]);
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) ans[i][j]=dis[i][j];
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
if(col[i]!=col[k]) continue;
for(int j=1;j<=n;j++)
{
if(col[j]==col[k] || vis[k][j]==false) continue;
dis2[i][j]=min(dis2[i][j],dis[i][k]+val[j]);
}
}
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
if(i==k) continue;
for(int j=1;j<=n;j++)
{
if(i==j || j==k) continue;
dis2[i][j]=min(dis2[i][j],max(dis2[i][k],dis2[k][j]));
}
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(col[k]==col[j])
ans[i][j]=min(ans[i][j],max(dis2[i][k],dis[k][j]));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) cout<<"0 ";
else cout<<ans[i][j]<<" ";
}
puts("");
}
}
return 0;
}
QOJ6306 Chase Game
可以发现当第二个人瞬移过来后，第一个人就一定是沿着最短路直接走到 \(n\) 了，此时这一部分的代价可以直接算出来。而至于第二个人还在点 \(k\) 的这一部分，可以给每个点赋上 \(D-dis_{k,u}\) 的点权然后跑 dij 求出到达某个点的最小代价。那么答案就分三种情况，一是只有第一部分，此时就是 dij 跑出来的到 \(n\) 的最短路；二是走了一步就直接进入第二部分，可以通过枚举 \(1\) 的出点求出；三是两个部分都有，枚举中转点和中转点的出点，两个部分代价相加即可。注意还需要两次 bfs 预处理出每个点到点 \(n\) 和点 \(k\) 的最短路。
struct node{
int to,nxt;
} edge[N<<1];
int n,m,k,D,tot,head[N],dis[N][2],val[N];
ll dist[N],ans=INF,w[N];
bool tmp[N],vis[N];
queue <int> Q;
priority_queue <PII,vector<PII>,greater<PII> >q;
void addedge(int u,int v)
{
edge[++tot].to=v,edge[tot].nxt=head[u],head[u]=tot;
}
void bfs(int s,int opt)
{
Q.push(s);
while(Q.empty()==false)
{
int u=Q.front();
Q.pop();
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v!=s && dis[v][opt]==0) dis[v][opt]=dis[u][opt]+1,Q.push(v);
}
}
}
void dij(int s)
{
for(int i=1;i<=n;i++) dist[i]=INF;
q.push({0,s}),dist[s]=0;
while(q.empty()==false)
{
PII p=q.top();
q.pop();
int u=p.second;
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(tmp[v]==false && dist[v]>dist[u]+val[v])
{
dist[v]=dist[u]+val[v];
if(vis[v]==false) q.push({dist[v],v});
}
}
}
}
int main()
{
n=read(),m=read(),k=read(),D=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
addedge(u,v),addedge(v,u);
}
bfs(n,0),bfs(k,1);
for(int i=1;i<=n;i++)
{
if(D-dis[i][1]>0) val[i]=D-dis[i][1];
else tmp[i]=true;
}
dij(1);
for(int i=0;i<=n;i++) w[i]=D-i%D;
for(int i=1;i<=n;i++) w[i]+=w[i-1];
ans=min(ans,dist[n]);//只走第一轮
for(int i=head[1];i;i=edge[i].nxt)//只走第二轮
{
int v=edge[i].to;
if(tmp[v]) ans=min(ans,w[dis[v][0]]);
}
for(int u=1;u<=n;u++)
{
if(tmp[u]) continue;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(tmp[v]) ans=min(ans,dist[u]+w[dis[v][0]]);
}
}
cout<<ans;
return 0;
}
洛谷P2371 [国家集训队] 墨墨的等式
同余最短路经典题，不再赘述。
洛谷P3623 [APIO2008] 免费道路
先对黑色边做一遍生成树，再把白色边加进去，那么此时加进去的白边是一定要加的。那么我们先将一定要加的那些白边加上，然后再补齐 \(k\) 条白边，最后把剩下的黑边加进去就行，本质上就是每次加一条白边产生环后删去一条环上的黑边。无解情况就是必须加的白边数量 \(\ge k\) 或者加不够 \(k\) 条白边或者图不连通。
洛谷P3639 [APIO2013] 道路费用
容易想到 \(2^k\) 去枚举这 \(k\) 条边的一个使用情况，然后再加入原图中的边来保持连通性，但复杂度显然有点高。我们不妨先只连上这 \(k\) 条边，然后尝试将原图中的 \(m\) 条边加入，直到图连通，此时后加入的那些原图上的边就是必须要加的，因为其它方案加入的新边的数量少了，那么这些后加入的边肯定也得选上，然后还可能再加另一些边。由于保证边权互不相同，因此后加入的那些边是固定的，所以可以将这些边先缩起来，缩完后点的数量就变成了 \(k+1\) 。同时由于新边数量的减少，所以可能还需要加入一些原图上的边，我们再把备用的边全部找出来，显然备用的边只会有 \(k\) 条。此时就可以套用原来的做法，\(2^k\) 去枚举选择情况，先加入新边，再加入备用的边使得整张图连通，然后对于计算新加入的边的代价，先考虑这些边的边权，事实上那些没有加入的备选边对新加入的边的边权进行了限制，它要求最小生成树上那两点之间的每条边的边权都必须小于它的边权，否则将最大的删去替换成它一定更优。由于点数很小，所以我们可以暴力跳路径求出每条边的最大边权。至于每条边的经过次数，以 \(1\) 所在的点为根 dfs 求出每个点子树内的人数即可。总时间复杂度为 \(O(m\log m+2^kk^2)\) 。
CF1628E Groceries in Meteor Town
前置题目：CF1062E Company 结论：一些节点的 LCA 一定是其中 dfs 序最小和 dfs 序最大的两个点的 LCA 。那么只需要对于每个询问区间，枚举是删掉 dfs 序最小的点还是 dfs 序最大的点，删掉后可以分成两个子区间，求出两个子区间的 LCA ，再求一下两个子区间的 LCA 的 LCA 就是删掉这个点后这段区间的 LCA ，然后两种情况比一下深度就行。
我们回到这道题上，它要求节点 \(x\) 到任意一个白色节点的简单路径上经过的边的最大权值，容易想到建 Kruskal 重构树，那么问题就转变成询问 \(x\) 与所有白色节点的 LCA 。根据上面的结论，可以转化成求白色节点与 \(x\) 中 dfs 序的最小值和最大值，可以用线段树进行维护，每个节点维护一个区间内白色节点的 dfs 序最小值和最大值，所有节点的 dfs 序最小值和最大值，以及一个更新的懒标记即可。
洛谷P3588 [POI2015] PUS
以前做过。
洛谷P3530 [POI2012] FES-Festival
以前做过。
gym104427B Lawyers
对于那些 \((u,v)\in E\) 且 \((v,u)\notin E\) 的边 \((u,v)\) ，我们选上它们一定是不劣的，因此我们先将这些边全部选上，并对相连的点进行标记，表示这些点已经有人辩护了。而至于剩下的一堆双向边，它们会形成若干个连通块，只有连通块含有长度大于 \(2\) 的环时才有解，事实上就是将双向边看成无向边后这个连通分量不能是一棵树，因此我们 bfs 的时候统计一下点数和边数然后判断即可。
int n,m;
bool vis[N],use[N];
set <int> out[N];
vector <int> in[N];
queue <int> q;
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
out[u].insert(v),in[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(in[i].empty())
{
puts("NO");
return 0;
}
}
for(int u=1;u<=n;u++)
{
if(vis[u]) continue;
for(auto v:in[u])
if(out[u].count(v)==0) vis[u]=true;
if(vis[u]==false) continue;
q.push(u);
while(q.empty()==false)
{
int u=q.front();
q.pop();
for(auto v:out[u])
if(vis[v]==false) vis[v]=true,q.push(v);
}
}
for(int u=1;u<=n;u++)
{
if(vis[u] || use[u]) continue;
q.push(u),use[u]=true;
int vcnt=0,ecnt=0;
while(q.empty()==false)
{
int u=q.front();
q.pop();
vcnt++;
for(auto v:in[u])
{
if(vis[v]==true) continue;
ecnt++;
if(use[v]==false) use[v]=true,q.push(v);
}
}
if(ecnt/2==vcnt-1)
{
puts("NO");
return 0;
}
}
puts("YES");
return 0;
}
洛谷P3225 [HNOI2012] 矿场搭建
以前做过。
洛谷P3119 [USACO15JAN] Grass Cownoisseur G
以前做过。
gym103427H/QOJ6019 Line Graph Matching
大力手玩可以发现当边数是偶数时，所有边都是可以匹配的。而至于奇数的情况，我们显然是舍弃掉边权最小的那一条边。但是这条边也有一些限制，考虑如果这条边是割边，对于删掉它后形成的两个连通分量，是需要满足边数都是偶数的，如果不是割边就没有别的要求了。因为如果都是奇数我们就还得删别的边，那么显然是不优的。然后就在符合条件的边集中选一条最小的删掉即可。
CF1062F Upgrading Cities
以前做过。