DAT4-5 图论
最短路
性质
记\(dis[u]\)代表从源点走到u的最短路长度
1.贪心性：源点到任意一个点最短路上的每一步都是一个最短路
2.存在性：两个点之间的最短路有可能不存在。（源点存在一个到达该点且经过一个负环的路径/图不连通）
3.三角形不等式：对于一条边\(u\stackrel{w}{\to}v\)，一定有\(dis[v]<=dis[u]+w\)
4.最短路图：从源点出发，把所有\(dis[v]=dis[u]+w\)的边建出来可以得到一张DAG。（不考虑0环）
算法
松弛操作：对于一条边，若当前\(dis[v]>dis[u]+w\)，则置\(dis[v]=dis[u]+w\)
1.Bellman-Ford(SPFA)
\(O(nm)\)
2.Dijkstra
朴素\(O(n^2)\)
堆优化\(O((n+m)log(n+m))\)
只用于正权图
3.Floyd
\(O(n^3)\)
4.Johnson
用Dijkstra跑全源最短路
解决负权边：增加点权\(h[u]\),将边的权值由\(w\)改为\(w+h[u]-h[v]\)
这样不会影响最短路大小比较
\(h[u]\)满足性质:\(w+h[u]-h[v]>=0\)，即\(h[v]<=w+h[u]\)
建立一个超级源点（防止有点遍历不到）跑Bellman-Ford，得到\(h[u]\)
\(O(nmlogm)\)
bool check(){
for(int i=1;i<=n;i++)h[i]=1e9;
queue<int>q;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(int j=0;j<a[u].size();j++){
int v=a[u][j].v,w=a[u][j].w;
if(h[v]>h[u]+w){
h[v]=h[u]+w;
q.push(v);
in[v]++;
if(in[v]>n+1)return 1;//判断负环，加上超级源点共n+1个点
}
}
}
return 0;
}
void dijkstra(int s){
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)d[i]=1e9;
d[s]=0;
priority_queue<node>q;
q.push(node{s,0});
while(!q.empty()){
node now=q.top();
q.pop();
if(vis[now.u])continue;
else vis[now.u]=1;
for(int j=0;j<a[now.u].size();j++){
int v=a[now.u][j].v,w=a[now.u][j].w;
if(d[v]>d[now.u]+w+h[now.u]-h[v]){
d[v]=d[now.u]+w+h[now.u]-h[v];
q.push(node{v,d[v]});
}
}
}
}
for(int i=1;i<=n;i++)a[0].push_back(edge{i,0});//建立超级源点
for(int i=1;i<=n;i++)dijkstra(i);//统计答案时特判路径不存在的情况
问题
1.输出方案
\(pre[i]\)记录前驱节点
2.传递闭包
bitset优化\(O(\frac{n^3}{w})\)
3.选择\(k\)条道路以\(c\)代价通行，求最短路
分层图 \(O(kmlogm)\)
for(int i=1;i<=m;i++){//P4568 P4822
int u=read()+1,v=read()+1,w=read();
a[u].push_back(edge{v,w});
a[v].push_back(edge{u,w});
for(int j=1;j<=k;j++){
a[u+j*n].push_back(edge{v+j*n,w});
a[v+j*n].push_back(edge{u+j*n,w});
a[u+(j-1)*n].push_back(edge{v+j*n,0});
a[v+(j-1)*n].push_back(edge{u+j*n,0});
}
}
4.给出一个\(N\)个顶点\(M\)条边的无向无权图，顶点编号为\(1∼N\),求从顶点\(1\)开始，到其他各点的最短路条数
void bfs(){//P1144
...
for(int v:a[u]){
if(d[v]>d[u]+1){
d[v]=d[u]+1;
f[v]=f[u];
q.push(v);
}else if(d[v]==d[u]+1){
f[v]=(f[v]+f[u])%p;
}
}
...
}
P1462
二分点权，最短路判定
不开longlong见祖宗
P1119
理解Floyd本质
void floyd(){
init();
int now=1;
while(q--){
int u=read()+1,v=read()+1,tim=read();
while(t[now]<=tim&&now<=n){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][now]+f[now][j]);
now++;
}
ask(u,v);
}
}
P1772
动态规划
枚举运输路线的更换时间\(j\)
\(f[i]=min(f[j-1]+(i-j+1)\times{}dijkstra(j,i)+k)),j\in{}[1,i]\)
dijkstra时忽略不可到达的点
最终结果为\(f[n]-k\)
ll dijkstra(ll tl,ll tr){
...
for(int j=0;j<a[now.u].size();j++){
ll v=a[now.u][j].v,w=a[now.u][j].w;
if(check(v,tl,tr)){//判断点是否可行
if(dist[v]>dist[now.u]+w){
dist[v]=dist[now.u]+w;
q.push(node{v,dist[v]});
}
}
}
...
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i]=min(f[i],f[j-1]+1ll*(i-j+1)*dijkstra(j,i)+k);
P2371
摆
并查集
void init(){//P3367
for(int i=1;i<=n;i++)f[i]=i;
}
int find(int i){
if(f[i]==i)return i;
else return f[i]=find(f[i]);//路径压缩优化
}
void merge(int i,int j){//合并
f[find(i)]=find(j);
}
bool query(int i,int j){//查询
return find(i)==find(j);
}
优化
1.路径压缩
2.按秩（启发式）合并
void init(){
for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;
}
void merge(int i,int j){
i=find(i),j=find(j);
if(i==j)return;
if(siz[i]>siz[j])swap(i,j);
f[i]=j;siz[j]+=siz[i];
}
任意一种优化单词均摊复杂度为\(O(logn)\)
全部使用复杂度为\(O(\alpha(n))\)
问题
1.维护每个集合的点权和/maxn
带权并查集
2.统计目前集合数量
for(int i=1;i<=n;i++)if(f[i]==i)ans++;
3.将某元素从集合A移动到集合B
修改根，维护信息
4.利用并查集维护\(n\)个命题，有\(m\)个条件
条件为\(p\Leftrightarrow q\)或\(p\Leftrightarrow\neg{}q\)两种
开正反两个并查集
注意：必要的时候舍弃“路径压缩”操作。因为它破坏了并查集的树结构。同时会造成一些复杂度错误。
P2024
//正反集
int f[150004];// 同类 敌人 食物
if(x>n||y>n||(x==y&&opt==2)){
ans++;
continue;
}
if(opt==1){
if(find(x+n)==find(y)||find(x+2*n)==find(y)){
ans++;
}else{
merge(x,y);
merge(x+n,y+n);
merge(x+2*n,y+2*n);
}
}else{
if(find(x)==find(y)||find(x+n)==find(y)||find(y+2*n)==find(x)){
ans++;
}else{
merge(x+2*n,y);
merge(x+n,y+2*n);
merge(x,y+n);
}
}
//带权并查集
int find(int i){
if(f[i]!=i){
int tmp=f[i];
f[i]=find(f[i]);
d[i]=(d[i]+d[tmp])%3;
return f[i];
}else return i;
}
if(w==1)w=0;
if(u==v&&w==2){
ans++;
}else if(u>n||v>n){
ans++;
}else{
int fu=find(u),fv=find(v);
if(fu!=fv){
f[fu]=fv;
d[fu]=(w+d[v]-d[u]+3)%3;
}else if((d[u]-d[v]+3)%3!=w){
ans++;
}
}
生成树
最小生成树：边权和最小的生成树。
瓶颈生成树：最大边权最小的生成树。
最小瓶颈路：两个点之间最大边权最小的简单路径。
性质：
最小生成树是瓶颈生成树的充分不必要条件，即一棵最小生成树一定是一棵瓶颈生成树，一棵瓶颈生成树不一定是一棵最小生成树。
最小生成树上两个点的路径一定是一个最小瓶颈路。
算法
1.Kruskal
\(O(mlogm)\)
2.Prim
\(O(mlogm)\)
问题
1.思考Kruskal的算法原理，求结点\(1\)到结点\(n\)的最小瓶颈路的权值
节点\(1\)所在集合与节点\(n\)所在集合合并时，kruskal所选的边权\(w\)即为结点\(1\)到结点\(n\)的最小瓶颈路的权值
2.并查集与Kruskal的算法关系密切。在不使用路径压缩的情况下，整张图的并查集会呈现一棵树的样貌。这棵树和最小生成树有什么关系
瓶颈路
3.比较Prim和Dijkstra算法的相似性。指出为何Prim可以处理负权边和Dijkstra不行
4.获得 “严格次小生成树”
void dfs(int i,int fa){//P4180
d[i]=d[fa]+1;
for(int j=1;(1<<j)<=d[i];j++){
dp[i][j]=dp[dp[i][j-1]][j-1];
g[i][j]=max(g[dp[i][j-1]][j-1],g[i][j-1]);
//维护次大值
h[i][j]=max(h[dp[i][j-1]][j-1],h[i][j-1]);
if(g[dp[i][j-1]][j-1]!=g[i][j-1]){
h[i][j]=max(h[i][j],min(g[dp[i][j-1]][j-1],g[i][j-1]));
}
}
for(int j=0;j<a[i].size();j++){
int v=a[i][j].v,w=a[i][j].w;
if(v!=fa){
dp[v][0]=i;
g[v][0]=w;
dfs(v,i);
}
}
}
int ask(int i,int j,int lim){
int ret=0;
if(d[i]<d[j])swap(i,j);
for(int k=dis;k>=0;k--){
if(d[i]-(1<<k)>=d[j]){
if(g[i][k]==lim)ret=max(ret,h[i][k]);
else ret=max(ret,g[i][k]);
i=dp[i][k];
}
}
if(i==j)return ret;
for(int k=dis;k>=0;k--){
if(dp[i][k]!=dp[j][k]){
if(g[i][k]==lim)ret=max(ret,max(h[i][k],h[j][k]));
else ret=max(ret,max(g[i][k],g[j][k]));
i=dp[i][k];
j=dp[j][k];
}
}
if(g[i][0]!=lim)ret=max(ret,g[i][0]);
if(g[j][0]!=lim)ret=max(ret,g[j][0]);
return ret;
}
void solve(){
ans=inf;
for(int i=1;i<=m;i++){
if(vis[i]&&e[i].u!=e[i].v){//判断自环
int tmp=ask(e[i].u,e[i].v,e[i].w);
ans=min(ans,sum+e[i].w-tmp);
}
}
cout<<ans;
}
init();
kruskal();//先求最小生成树
dfs(1,0);//预处理最大值和次大值
solve();//用未选边替换，更新答案
6.思考最小生成树构建时的贪心性质，简要解释为何最小生成树不止一个
P1967
求最大生成树
在生成树上倍增预处理最小值
lca查询最小值
void dfs(int i,int fa){
d[i]=d[fa]+1;
col[i]=nums;
for(int j=1;(1<<j)<=d[i];j++){
dp[i][j]=dp[dp[i][j-1]][j-1];
maxn[i][j]=min(maxn[dp[i][j-1]][j-1],maxn[i][j-1]);
}
for(int j=0;j<a[i].size();j++){
int v=a[i][j].y,w=a[i][j].z;
if(v!=fa){
dp[v][0]=i;
maxn[v][0]=w;
dfs(v,i);
}
}
}
int ask(int i,int j){
int ret=0x3f3f3f3f;
if(d[i]<d[j])swap(i,j);
for(int k=dis;k>=0;k--){
if(d[i]-(1<<k)>=d[j]){
ret=min(ret,maxn[i][k]);
i=dp[i][k];
}
}
if(i==j)return ret;
for(int k=dis;k>=0;k--){
if(dp[i][k]!=dp[j][k]){
ret=min(ret,min(maxn[i][k],maxn[j][k]));
i=dp[i][k];
j=dp[j][k];
}
}
return min(ret,min(maxn[i][0],maxn[j][0]));
}
init();//预处理
kruskal();//求生成树
for(int i=1;i<=n;i++){
if(!d[i]){
nums++;//图不连通
dfs(i,0);
}
}
solve();//查询
CF1513D
摆
树上倍增
求lca
void init(int i,int fa){//P3379
d[i]=d[fa]+1;
f[i][0]=fa;
for(int j=1;(1<<j)<=d[i];j++){
f[i][j]=f[f[i][j-1]][j-1];
}
for(int j=0;j<a[i].size();j++){
int v=a[i][j];
if(v!=fa){
init(v,i);
}
}
}
int lca(int i,int j){
if(d[j]>d[i])swap(i,j);
for(int k=stp;k>=0;k--){//k>=0注意
if(d[i]-(1<<k)>=d[j]){
i=f[i][k];
}
}
if(i==j)return i;
for(int k=stp;k>=0;k--){//k>=0
if(f[i][k]!=f[j][k]){
i=f[i][k];
j=f[j][k];
}
}
return f[i][0];
}
init(s,0);
lca(i,j);
问题
1.求出 k 个点的树上最近公共祖先
2.将k个点两两求树上最近公共祖先
P4281
暴力去找
pair<int,int> ask(int i,int j){
int ret=0;
if(d[i]<d[j])swap(i,j);
for(int k=dis;k>=0;k--){
if(d[i]-(1<<k)>=d[j]){
ret+=dp[i][k];
i=f[i][k];
}
}
if(i==j)return make_pair(i,ret);
for(int k=dis;k>=0;k--){
if(f[i][k]!=f[j][k]){
ret+=dp[i][k]+dp[j][k];
i=f[i][k];
j=f[j][k];
}
}
return make_pair(f[i][0],ret+2);
}
pair<int,int> getp(int A,int B,int C){
pair<int,int> tmp=ask(B,C);
pair<int,int> ans=ask(tmp.first,A);
return make_pair(tmp.first,tmp.second+ans.second);
}
while(m--){
int x=read(),y=read(),z=read();
pair<int,int> t1=getp(y,z,x),t2=getp(x,z,y),t3=getp(z,y,x);
if(t1.second>t2.second)swap(t1,t2);
if(t1.second>t3.second)swap(t1,t3);
cout<<t1.first<<" "<<t1.second<<endl;
}
树上差分
查询
1.求树上路径经过点的个数
\(=dep[u]+dep[v]-dep[fa[lca]]-dep[lca]\)
2.求树上路径的边权和
\(=dist[u]+dist[v]-2\times{}dist[lca]\)
修改
在\(p\rightarrow{}q\)路径上的每个点点权\(+v\)
\(val[p]=val[p]+v\)
\(val[q]=val[q]+v\)
\(val[lca]=val[lca]-v\)
\(val[f[lca]]=val[f[lca]]-v\)
dfs自下向上查询
P2680
运输计划为树上一条路径
使得运输时间最长的计划运输时间最短，二分
对于大于\(mid\)的运输计划，找到这些运输计划共同经过的最大边
判断共同经过使用树上差分
inline卡常
inline void dfs(int i,int fa){
for(int j=0;j<a[i].size();j++){
int v=a[i][j].v,w=a[i][j].w;
if(v!=fa){
dfs(v,i);
val[i]+=val[v];
}
}
for(int j=0;j<a[i].size();j++){//在更新完val[]后再判断
int v=a[i][j].v,w=a[i][j].w;
if(v!=fa){
if(val[i]==cnt&&val[v]==cnt){//该边被cnt条路径经过
dmax=max(dmax,w);
}
}
}
}
inline bool check(ll x){
maxn=0;dmax=0;cnt=0;//最长运输计划耗时 可减少的最大时间 需要减少时间的边数
memset(val,0,sizeof val);//注意
for(int i=1;i<=m;i++){
if(q[i].w>x){
int u=q[i].u,v=q[i].v;
maxn=max(maxn,q[i].w);cnt++;
int Lca=getsum(u,v).first;
//树上差分
val[u]++;
val[v]++;
val[Lca]--;
val[f[Lca][0]]--;
}
}
dfs(1,0);
return maxn-dmax<=x;
}
ll l=0,r=maxn;
while(l<r){
ll mid=l+(r-l)/2;
if(check(mid))r=mid;
else l=mid+1;
}
hdu6053
难
有一棵树，有\(n\)个节点，每个节点都有一个用整数表示的颜色类型，其中节点\(i\)的颜色是\(c_i\)
每两个不同节点之间的路径是唯一的，我们定义路径的值为其中出现的不同颜色的数量
计算所有路径的值的总和，该树上总共有\(\frac{n(n-1)}{2}\)条路径
定义\([P]\)若\(P\)为真则为\(1\),否则为\(0\)
即求
\({\textstyle \sum_{i=1}^{\frac{n(n-1)}{2}}}{\textstyle\sum_{j=1}^{colnums}[c_j出现次数>=1]}\)
\(={\textstyle \sum_{j=1}^{colnums}{\textstyle\sum_{i=1}^{\frac{n(n-1)}{2}}}[c_j出现次数>=1]}\)
\(=colnums\times\frac{n(n-1)}{2}-{\textstyle \sum_{j=1}^{colnums}{\textstyle\sum_{i=1}^{\frac{n(n-1)}{2}}}[c_j出现次数=0]}\)
// 以1节点为根
ll fi(ll i){//i为连通块大小,返回连通块边数
return i*(i-1)/2;
}
void dfs(int i,int fa){
//sum[i]表示当前以i颜色节点为根的子树大小
ll inssum=0;//记录增长
siz[i]=1;//siz[i]表示以节点i为根的子树大小
for(int j=0;j<a[i].size();j++){
int v=a[i][j];
if(v!=fa){
ll pre=sum[c[i]];//记录过去大小
dfs(v,i);//递归子树
siz[i]+=siz[v];//更新
ll ins=sum[c[i]]-pre;//递归子树之后，sum[c[i]]的增长值，也就是子树内以i颜色节点为根的子树大小
sub+=fi(siz[v]-ins);//子树大小-ins即为颜色c[i]不出现的连通块大小
inssum+=ins;//记录
}
}
sum[c[i]]+=siz[i]-inssum;//加上以当前节点为根的子树内的其它节点个数
}
void solve(){
dfs(1,0);//统计sub,sub为每种颜色未出现边数之和
for(int i=1;i<=n;i++)
cnt+=(csum[i]>0);//统计颜色种类
//统计每种颜色最浅节点到根之间的贡献
vis[c[1]]=1;
for(int i=1;i<=n;i++){
if(!vis[c[i]]){
sub+=fi(n-sum[c[i]]);
vis[c[i]]=1;
}
}
ans=cnt*fi(n)-sub;
++cas;
printf("Case #%lld: %lld\n",cas,ans);
}
Clear();//注意
for()csum[c[i]]++;//统计每种颜色出现次数
solve();
P4768
P1600
P3953
P1084
摆
标签：return,int,ret,find,--,D4,集训,dp From： https://www.cnblogs.com/wertyuio1/p/18365256