[IAMOI R1] 走亲访友题解

· · 题解

Subtask1

考虑随便搜出一棵生成树，然后删掉剩余 m-n+1 条边，从起点开始，每次从当前点暴力跑 dfs 走到下一条要删的边的端点（这样可以保证走的点之前没有被删过），然后删掉这条边就行。

总共经过 m-n+1 轮，每轮最多走 m 条边，因此边数最多为 m(m-n+1)，复杂度是 O(m^2)。

Subtask2

把暴力跑 dfs 换成暴力跑树边就能把复杂度降至 O(nm)。

Subtask3

依然沿用 Subtask1 的做法，边数是 n 条，复杂度是 O(n+m)。

Subtask4

考虑贴近正解。

如果没有“删除一条边后就不能再走”的限制这题是简单的，直接把每条边都遍历一遍就行了。

添加这个要求后，我们就要考虑如何不重复地经过每条边。

考虑到“不重复”，可以想到欧拉回路（欧拉路径也是一样）。对于原图是欧拉图的情况，总步数可以不超过 m。因为我们可以跑一遍欧拉回路，每遍历到一条边，若它是树边则不删去，否则删去。欧拉回路是为了保证每条边可以不重不漏地走一次。

否则的话原图存在奇度点，考虑把这些奇度点“去掉”。事实上，我们跑出来的路径不一定要是严格的欧拉回路。因为一条边实际上可以经过多次，我们只需要再最后删除就行了。我们可以给每条路径新增一个“通过次数”。我们可以给奇度点两两分组，给每组组内两个点间的任意简单路径上的每条边的“通过次数”都加一，可以看做将该路径复制一遍（以下简称加边），使得原图转化为欧拉图。

这样最多有 \frac{n}{2} 组，每组最多加 n-1 条边，总边数控制在 m+\frac{n(n-1)}{2} 内。

然而如果暴力跑 dfs 时间复杂度是 O(nm) 的，依然可以通过把暴力跑 dfs 换成暴力跑树边，复杂度做到 O(n^2+m)。

Subtask5

你已经非常接近正解了！

考虑优化一下分组，使得新加入的边尽量少。

可以这样加边：搜一遍生成树，在回溯时若该点为奇度点，则将该点与其父亲节点加边。

可以证明这样加完边后原图一定是欧拉图。

简单证明：用这样的操作，因为回溯时才加边保证了非根节点一定可以变成偶度点，而每一次加边，节点度数和的奇偶性不变，一开始是偶数个，加完边后也是偶数个，又因为没有其他偶度点了，所以根节点也是偶度点。

这样，就在每条树边最多复制一次的情况下让每个点的度数均变成了偶数。

理一遍思路：直接跑生成树，给树边打标记，奇度点加边，跑欧拉回路输出路径。

总边数 m+n-1 条，复杂度 O(n+m)。

std：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=5e5+5;
int n,m,s,u,v,cnt=1,cntans,to[N+M<<1],id[N+M<<1],nxt[N+M<<1],h[N],d[N],ans[N+M];
bool tag[M],vis[N+M<<1];
void save(int u,int v,int w){
    to[++cnt]=v;
    id[cnt]=w;
    nxt[cnt]=h[u];
    h[u]=cnt;
    d[u]++;
}
void dfs(int u){
    vis[u]=1;
    for(int i=h[u];i;i=nxt[i]){
        if(vis[to[i]]||i>(m<<1|1)) continue;
        tag[id[i]]=1;
        dfs(to[i]);
        if(d[to[i]]&1){
            save(u,to[i],id[i]);
            save(to[i],u,id[i]);
        }
    }
}
void dfs2(int u){
    for(int &i=h[u];i;i=nxt[i]){
        if(vis[i]) continue;
        vis[i]=vis[i^1]=1;
        int k=id[i];
        dfs2(to[i]);
        ans[++cntans]=k;
    }
}
int main(){
    scanf("%d%d%*d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        save(u,v,i);
        save(v,u,i);
    }
    dfs(s);
    memset(vis,0,sizeof(vis));
    dfs2(s);
    printf("%d\n",cntans);
    for(int i=cntans;i>=1;i--) printf("%d %d\n",ans[i],(int)tag[ans[i]]);
    return 0;
}