XCPC Notes

Appearance

发布时间：2024-07-24

欧拉路径和欧拉回路 ​

概念 ​

  • 在一个图中，一条路径能将所有边都走且仅走一遍的路径，为欧拉路径
  • 欧拉回路是特殊的欧拉路径，即起点等于终点

存在欧拉路径和欧拉回路的条件 ​

  1. 在无向图中，所有点连通
    • 存在欧拉路径：度数为奇数的点有0个或2个
    • 存在欧拉回路：度数为奇数的点有0个
  2. 在有向图中，所有点连通
    • 存在欧拉路径：要么所有点出度等于入度；要么除了两个点出度等于入度 剩余两个点：一个点出度比入度多1(起点)，一个点入度比出度多1(终点)
    • 存在欧拉回路：所有点出度等于入度

UVA10203 铲雪车 ​

题意：
给定一张无向图，需要对边的两个方向铲两次雪，铲雪的速度和不铲的速度已知，问最少花多少时间
思路：
将无向边变成两条相反的有向边，所有点入度等于出度，存在欧拉回路，因此时间即为总路程*2/铲雪速度

UOJ117 欧拉回路(模板) ​

题意：
找无向图或者有向图的欧拉回路
优化：

  • 欧拉路径是遍历边而不是点，每次要将边删去，复杂度才会是线性
  • 改法：每次遍历后，让h[u]=ne[i] 其次是遍历改成i=h[u];~i;i=h[u]，一直让它等于h[u]，保证儿子能影响父亲
cpp
int e[M],ne[M],h[N],idx;
int din[N],dout[N];
bool used[M];
int n,m,ans[M],cnt,type;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
    for(int i=h[u];~i;i=h[u]){
        if(used[i]){
            h[u]=ne[i];
            continue;
        }
        used[i]=1;
        if(type==1)used[i^1]=1;
        h[u]=ne[i];
        dfs(e[i]);
        int t;
        if(type==1){
            t=i/2+1;
            if(i&1)t=-t;
        }
        else t=i+1;
        ans[++cnt]=t;
    }
}
void solve(){
    cin>>type>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        din[b]++,dout[a]++;
        if(type==1)add(b,a);
    }
    if(type==1){
        for(int i=1;i<=n;i++){
            if(din[i]+dout[i]&1){
                cout<<"NO\n";
                return;
            }
        }
    }
    else{
        for(int i=1;i<=n;i++){
            if(din[i]!=dout[i]){
                cout<<"NO\n";
                return;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(h[i]!=-1){
            dfs(i);
            break;
        }
    }
    if(cnt<m){x
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
    for(int i=cnt;i;i--)cout<<ans[i]<<" ";
}

P7771 【模板】欧拉路径(有向图输出字典序最小) ​

思路：

  • 坑点：字典序最大反过来找不会是字典序最小
  • 欧拉路径是逆序输出的，先遍历的点在数组中位置越后，逆序后就越前
  • 只需要按照当前字典序最小的点先走即可，逆序输出即为字典序最小
cpp
int n,m;
vector<int> adj[N];
int del[N],din[N],dout[N],ans[M],cnt;
void dfs(int u){
    for(int i=del[u];i<adj[u].size();i=del[u]){
        del[u]=i+1;
        dfs(adj[u][i]);
        ans[++cnt]=adj[u][i];
    }
}
void solve(){
    cin>>n>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        dout[u]++,din[v]++;
        adj[u].push_back(v);
    }
    for(int i=1;i<=n;i++)sort(adj[i].begin(),adj[i].end());
    bool in=0,out=0;
    int start=1;
    for(int i=1;i<=n;i++){
        if(din[i]!=dout[i]){
            if(din[i]==dout[i]+1){
                if(in){
                    cout<<"No\n";
                    return;
                }
                in=1;
            }
            else if(dout[i]==din[i]+1){
                if(out){
                    cout<<"No\n";
                    return;
                }
                out=1;
                start=i;
            }
            else{
                cout<<"No\n";
                return;
            }
        }
    }
    if(in^out){
        cout<<"No\n";
        return;
    }
    dfs(start);
    ans[++cnt]=start;
    for(int i=cnt;i;i--)cout<<ans[i]<<" ";
}

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences(无向图输出字典序最小) ​

cpp
int m;
vector<PII> adj[N];
int del[N],ans[M],cnt,idx;
bool used[M];
void dfs(int u){
    for(int i=del[u];i<adj[u].size();i=del[u]){
        auto &[v,id]=adj[u][i];
        del[u]=i+1;
        if(used[id])continue;
        used[id]=used[id^1]=true;
        dfs(v);
        ans[++cnt]=v;
    }
}
void solve(){
    cin>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        adj[u].emplace_back(v,idx++);
        adj[v].emplace_back(u,idx++);
    }
    for(int i=1;i<=500;i++)sort(adj[i].begin(),adj[i].end());
    bool g=0;
    for(int i=1;i<=500;i++){
        if(adj[i].size()%2){
            dfs(i);
            ans[++cnt]=i;
            g=1;
            break;
        }
    }
    for(int i=1;i<=500;i++){
        if(adj[i].size()&&!g){
            dfs(i);
            ans[++cnt]=i;
            break;
        }
    }
    for(int i=cnt;i;i--)cout<<ans[i]<<"\n";
}

UVA10129 单词 Play on Words ​

题意：

  • 两个单词的尾部和头部字母相同就能连接
  • 给定多个单词，问能否拼接成在一起 思路：
  • 题意即问有向图是否存在欧拉回路
  • 并查集判断是否全部连通
  • 要么全部入度等于出度，要么入度多一和出度多一的点各一个

P3520 [POI2011] SMI-Garbage(找出全部简单环) ​

题意：
n个点m条边，边有0和1两种状态，每走一次边就会改变一种状态
每次只能走环形路径并且除了起点外其他点只能经过一次 给定m条边的初始状态数和目标状态数
问是否存在方案
思路：

  • 即找多个简单环，转化为欧拉路径
  • 对于始末状态相同的点，可以拆成两条边，删去这两条边，度数减2，不影响欧拉回路的性质
  • 即每个点入度等于出度
  • 使用类似tarjan算法的方法判环
cpp
vector<PII> adj[N];
int idx,cnt,del[N],stk[M],top;
vector<int> ans[M];
bool used[M],in_stack[N];
void dfs(int u){
    for(int i=del[u];i<adj[u].size();i=del[u]){
        auto &[v,id]=adj[u][i];
        del[u]=i+1;
        if(used[id])continue;
        used[id]=used[id^1]=true;
        dfs(v);
    }
    if(in_stack[u]){
        cnt++;
        int y;
        ans[cnt].push_back(u);
        do{
            y=stk[top--];
            in_stack[y]=false;
            ans[cnt].push_back(y);
        }while(y!=u);
    }
    //即使在栈中弹出后，要重新加进来
    in_stack[u]=true;
    stk[++top]=u;
}
void solve(){
    int n,m;
    cin>>n>>m;
    while(m--){
        int a,b,s,t;
        cin>>a>>b>>s>>t;
        if(s==t)continue;
        adj[a].emplace_back(b,idx++);
        adj[b].emplace_back(a,idx++);
    }
    int c=0;
    for(int i=1;i<=n;i++)sort(adj[i].begin(),adj[i].end()),c+=adj[i].size()%2;
    if(c){
        cout<<"NIE\n";
        return;
    }
    for(int i=1;i<=n;i++)dfs(i);
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<ans[i].size()-1<<" ";
        for(auto &x:ans[i])cout<<x<<" ";
        cout<<"\n";
    }
}

P3443 [POI2006] LIS-The Postman ​

题意：
找欧拉回路，并且回路包含给定的序列
思路：

  • 对于序列的一条边，不能有多个前驱后继，必须在原图存在
  • 一种做法是将边全部删去，换成一条边，这样比较难调
  • 另一种做法是打标记，只保留前面最前面的边，在dfs输出时如果有后缀边就一直按照这条路走即可

Wenwei Lin · 2022 — 2025