ZR 集训 Day26 – 图论进阶

ooliver 发布于 18 小时前 126 次阅读 OI

AI 摘要

当差分约束遇上01-BFS，当三元环碰上容斥——图论进阶的每一题都是一次思维爆破。二分答案、分层图、朱刘算法……掌握这些利器，再难的问题也能轻松拆解。

一些笔记

差分约束

2-SAT

三元环枚举

最小树形图

定义：有向图的最小生成树。

算法：

  1. 朴素算法：朱刘算法（见下面的例题）
  2. 最优算法：Tarjan 优化朱刘算法（待学习）

P1948 [USACO08JAN] Telephone Lines S

考虑二分答案 $x$，将边权大于 $x$ 的边权设为 $1$，其余设成 $0$，跑一遍 01-BFS，如果长度小于或等于 $k$ 即满足条件。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e3+5;
int n,m,k;
int dis[N],vis[N];
vector<pair<pair<int,int>,int>> e;
vector<pair<int,int>> g[N];

bool check(int x){
    for(int i=1;i<=n;i++) g[i].clear(),dis[i]=1e9,vis[i]=0;
    for(auto[node,w]:e){
        auto[u,v]=node;
        g[u].push_back({v,(w>x)});
        g[v].push_back({u,(w>x)});
    }
    deque<int> q;
    q.push_front(1);
    dis[1]=0;
    while(q.size()){
        int u=q.front();
        q.pop_front();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto[v,w]:g[u]){
            if(w+dis[u]<=dis[v]){
                dis[v]=w+dis[u];
                if(w) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
    if(dis[n]<=k) return 1;
    return 0;
}

signed main(){
    cin>>n>>m>>k;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        e.push_back({{u,v},w});
    }
    int l=0,r=1e6+5;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(l==1e6+5) cout<<-1;
    else cout<<l;
    return 0;
}

AT_agc056_c [AGC056C] 01 Balanced

差分约束题。

朴素的想法是设 $sum_i$ 表示 $0$ 的数量的前缀和，那就有以下约束：

$$
\begin{aligned}
sum_r-sum_l &= \frac{(r-l+1)}{2} \\
sum_i &\ge sum_{i-1} \\
sum_i &\le sum_{i-1}+1 \\
\end{aligned}
$$

但是如果根据这个关系建边，就会出现负边权，跑 SPFA 可能会被卡，所以考虑转化建边方法。

因为等式的约束是一定存在的，为了没有负边权，我们考虑将等式右边变成 $0$。那我们可以考虑重新定义数组 $sum$：

$$
sum_i=sum_{i-1}+\begin{cases}
1 &\text{if} s[i]='0' \\
-1 &\text{if} s[i]='1' \\
\end{cases}
$$

这样一来就得到了新的约束：

$$
\begin{aligned}
sum_l &= sum_r \\
sum_i &\le sum_{i-1} +1 \\
sum_{i-1} + 1 &\le sum_{i}+1 \\
\end{aligned}
$$

由于 $sum$ 表示的是 $0$ 的数量减 $1$ 的数量，所以跑差分约束、最大化 $sum$ 就能得到字典序最小的解。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,m;
int dis[N],vis[N];
vector<pair<int,int>> g[N];

void dij(){
    priority_queue<pair<int,int>> q;
    memset(dis,0x3f,sizeof dis);
    q.push({0,0});
    dis[0]=0;
    while(q.size()){
        auto[d,u]=q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto[v,w]:g[u]){
            if(!vis[v]&&dis[u]+w<=dis[v]){
                dis[v]=dis[u]+w;
                q.push({-dis[v],v});
            }
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        g[l-1].push_back({r,0});
        g[r].push_back({l-1,0});
    }
    for(int i=1;i<=n;i++){
        g[i].push_back({i-1,1});
        g[i-1].push_back({i,1});
    }
    dij();
    for(int i=1;i<=n;i++) cout<<(dis[i]<dis[i-1]);
    return 0;
}

P1989 【模板】无向图三元环计数

三元环计数模板，上面有步骤与复杂度分析。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,ans;
int deg[N],tag[N];
vector<pair<int,int>> e;
vector<int> g[N];

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e.push_back({u,v});
        deg[u]++,deg[v]++;
    }
    for(auto[u,v]:e){
        if(deg[u]>deg[v]||(deg[u]==deg[v]&&u>v)) swap(u,v);
        g[u].push_back(v);
    }
    for(int u=1;u<=n;u++){
        for(int v:g[u]) tag[v]=1;
        for(int v:g[u]) for(int w:g[v]) if(tag[w]) ans++;
        for(int v:g[u]) tag[v]=0;
    }
    cout<<ans;
    return 0;
}

CF229C Triangles

乍一看是三元环计数，但是和三元环计数没什么关系。

考虑将选出的边和未被选出的边染成两种颜色，那答案就是求完全图中颜色相同的三元环的数量，容斥一下就是 $C_n^3$ 减去颜色不同的三角形的数量。

考虑计算颜色相同的角的个数，应该等于颜色相同的三元环的数量乘三加上颜色不同的三角形的数量，设其为 $cnt$，有：

$$
\begin{aligned}
ans&=C_n^3-(cnt-3\times ans) \\
&=\frac{cnt-C_n^3}{2}
\end{aligned}
$$

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int n,m,cnt;
int deg[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++){
        int c1=deg[i],c2=n-1-deg[i];
        cnt+=c1*(c1-1)/2+c2*(c2-1)/2;
    }
    cout<<(cnt-n*(n-1)*(n-2)/6)/2;
    return 0;
}

P3547 [POI 2013] CEN-Price List

考虑答案的三种可能：

  1. 只走 $a$
  2. 都走
  3. 只走 $b$

对于前两种可能性，我们直接跑 BFS 即可。

对于第三种情况，我们考虑找到所有 $u \rightarrow v \rightarrow w$，且 $u$，$w$ 之间没有边，然后使 $u$ 花费 $b$ 的代价跳到 $w$。这样正确性显然，但是复杂度会爆炸。根据 BFS 的性质，我们知道，$w$ 第一次作为终点必然得到的就是最小的长度，所以我们把 $u \rightarrow v \rightarrow w$ 这条路径中的两条边分为两类，一类是起点边，一类是终点边。具体地，我们先枚举起点边，再枚举终点边，如果答案得到更新，就把终点边从边集中删去。

不难发现，一个三元环会被遍历三遍，其余的一边就被删掉了，所以复杂度可以看成 $O(m\sqrt(m))$。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,k,a,b;
int dis1[N],dis2[N],tag[N];
vector<int> g[N],t[N];

void bfs1(int s){
    memset(dis1,0x3f,sizeof dis1);
    queue<int> q;
    q.push(s);
    dis1[s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(dis1[u]+1<dis1[v]){
                dis1[v]=dis1[u]+1;
                q.push(v);
            }
        }
    }
}

void bfs2(int s){
    memset(dis2,0x3f,sizeof dis2);
    queue<int> q;
    q.push(s);
    dis2[s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v:g[u]) tag[v]=1;
        for(int v:g[u]){
            for(int i=0;i<t[v].size();i++){
                int w=t[v][i];
                if(tag[w]) continue;
                if(dis2[u]+b<dis2[w]){
                    dis2[w]=dis2[u]+b;
                    q.push(w);
                    swap(t[v][i],t[v][t[v].size()-1]);
                    t[v].pop_back();
                    i--;
                }
            }
        }
        for(int v:g[u]) tag[v]=0;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>a>>b;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        t[u].push_back(v);
        t[v].push_back(u);
    }
    bfs1(k);
    bfs2(k);
    for(int i=1;i<=n;i++){
        int ans=2e9;
        ans=min(ans,dis1[i]*a);
        ans=min(ans,(dis1[i]/2)*b+(dis1[i]&1)*a);
        ans=min(ans,dis2[i]);
        cout<<ans<<"\n";
    }
    return 0;
}

P5100 [JOI 2017 Final] 足球 / Soccer

不难发现，球移动时有三种状态：

  1. 带球移动
  2. 被横向踢走
  3. 被纵向踢走

考虑对三种状态建分层图，因为踢球时需要额外的代价 $B$，我们可以看作其是连接“带球移动层”和“被踢走”的层的边的边权。对于从“被踢走”层回到“带球移动层”，我们需要找到离当前点最近的人，这个 BFS 预处理一下即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define id(x,y) ((x)*(w+1)+(y))
#define add(x,y,z) g[(x)].push_back({(y),(z)})
#define int long long

const int N=1e6+5;
const int M=505;
int n,h,w,a,b,c;
int dis1[M][M],dis[N],tag[M][M],vis[N],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
vector<pair<int,int>> d,g[N];

void bfs(){
    queue<pair<int,int>> q;
    for(auto[x,y]:d) dis1[x][y]=0,q.push({x,y});
    while(q.size()){
        auto[x,y]=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||nx>h||ny<0||ny>w) continue;
            if(!dis1[nx][ny]&&!tag[nx][ny]){
                dis1[nx][ny]=dis1[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
}

void dij(){
    memset(dis,0x3f,sizeof dis);
    priority_queue<pair<int,int>> q;
    q.push({0,id(d[0].first,d[0].second)});
    dis[id(d[0].first,d[0].second)]=0;
    while(q.size()){
        auto[ddd,u]=q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto[v,wis]:g[u]){
            if(!vis[v]&&dis[u]+wis<dis[v]){
                dis[v]=dis[u]+wis;
                q.push({-dis[v],v});
            }
        }
    }
}

signed main(){
    cin>>h>>w>>a>>b>>c>>n;
    for(int i=1,x,y;i<=n;i++){
        cin>>x>>y;
        tag[x][y]=1;
        d.push_back({x,y});
    }
    bfs();
    for(int x=0;x<=h;x++) for(int y=0;y<=w;y++){
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||nx>h||ny<0||ny>w) continue;
            add(id(x,y),id(nx,ny),c);
            if(i<2) add(id(x,y)+(h+1)*(w+1),id(nx,ny)+(h+1)*(w+1),a);
            else add(id(x,y)+2*(h+1)*(w+1),id(nx,ny)+2*(h+1)*(w+1),a);
        }
        add(id(x,y),id(x,y)+(h+1)*(w+1),b);
        add(id(x,y)+(h+1)*(w+1),id(x,y),c*dis1[x][y]);
        add(id(x,y),id(x,y)+2*(h+1)*(w+1),b);
        add(id(x,y)+2*(h+1)*(w+1),id(x,y),c*dis1[x][y]);
    }
    dij();
    cout<<dis[id(d[d.size()-1].first,d[d.size()-1].second)];
    return 0;
}

P5663 [CSP-J 2019] 加工零件

考虑找到 $1$ 到 $a$ 的最短路 $dis_a$，这个最短路可以通过反复走一些边变成长度为 $dis_a+2k(k\in \mathbb{N})$。这是不难发现，这些路径的奇偶性是一致的。所以为了覆盖全部答案，我们在求最短路时要对路径长度的奇偶性分类，其余就没什么了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,q;
int dis[N][2];
vector<int> g[N];

void bfs(){
    memset(dis,0x3f,sizeof dis);
    queue<pair<int,bool>> q;
    q.push({1,0});
    dis[1][0]=0;
    while(q.size()){
        auto[u,d]=q.front();
        q.pop();
        for(int v:g[u]){
            if(dis[u][d]+1<dis[v][!d]){
                dis[v][!d]=dis[u][d]+1;
                q.push({v,!d});
            }
        }
    }
}

signed main(){
    cin>>n>>m>>q;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    while(q--){
        int a,l;
        cin>>a>>l;
        if(dis[a][l&1]<=l) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

P4716 【模板】最小树形图

这里介绍复杂度为 $O(nm)$ 的朱刘算法，算法流程如下：

  1. 对每个非根点选择最小入边（注意自环）
  2. 若某个非根点不存在入边，则无解
  3. 将每个最小入边加入答案
  4. 找环并缩点
  5. 如果没有环，返回答案
  6. 给每个点的入边减去其最小入边的边权
  7. 继续循环

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,r;
int in[N],fa[N],tag[N],id[N];
vector<pair<pair<int,int>,int>> e;

int solve(int root){
    int ans=0;
    while(1){
        for(int i=1;i<=n;i++) in[i]=1e10,tag[i]=id[i]=-1;
        for(auto[node,w]:e){
            auto[u,v]=node;
            if(w<in[v]&&u!=v) in[v]=w,fa[v]=u;
        }
        for(int i=1;i<=n;i++) if(i!=root&&in[i]>=1e10) return -1;
        in[root]=0;
        int idx=0,cnt=0;
        for(int i=1;i<=n;i++){
            ans+=in[i];
            int u=i;
            while(tag[u]!=i&&id[u]==-1&&u!=root) tag[u]=i,u=fa[u];
            if(id[u]==-1&&u!=root){    
                id[u]=++idx;
                int v=fa[u];
                while(v!=u) id[v]=idx,v=fa[v];
            }
        }
        if(!idx) return ans;
        for(int i=1;i<=n;i++) if(id[i]==-1) id[i]=++idx;
        for(auto&[node,w]:e){
            auto&[u,v]=node;
            if(id[u]!=id[v]) w-=in[v];
            u=id[u],v=id[v];
        }
        n=idx,root=id[root];
    }
    return ans;
}

signed main(){
    cin>>n>>m>>r;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        e.push_back({{u,v},w});
    }
    cout<<solve(r);
    return 0;
}