2021.1.28

Description

给定图无向图 \(G=(V,E)\)。\(Q\) 个询问，每次新增一条边，问新图 \(G'\) 至少需要多少条不相交的路径使得边被完美覆盖。

Solution

如果图 \(G\) 中只有恰好 0 个或 2 个奇度数的点，那么一条欧拉路径便可以完美覆盖。容易证明无论怎么加边，图中只有偶数个奇度数点。考虑有 \(2n\) 个奇度数点，将其划分为 \(n\) 组，每组之中的两个点两边。连边后图中就不存在奇度数点了，那么一定可以用一个欧拉回路覆盖。将这个欧拉回路提取出来，本质是一个环。将之前新加的 \(n\) 条边删掉，就得到了 \(n\) 条链，即 \(n\) 条路径。容易知道这 \(n\) 条路径恰好能完美覆盖所有边。所以有 \(Ans\leq n\)

而我们又知道，一条路径至多能消灭两个奇度数的点，所以 \(Ans\geq n\)。综上，\(Ans=n\) 。

那么我们只需要动态统计有多少个奇度数点就可以了，答案即其二分之一。

对于非联通的图，需要用并查集来维护，但也很好写。

#include<stdio.h>
#define N 1000007

inline int read(){
   int x=0,flag=1; char c=getchar();
   while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
   while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
   return flag? x:-x;
}

int n,m,Q,fa[N],cnt[N],ans=0;
bool vis[N],tag[N];

inline int find(int x){
   if(fa[x]==x) return x;
   return fa[x]=find(fa[x]);
}

inline int calc(int x){return cnt[x]? cnt[x]>>1:tag[x];}

void Link(int u,int v){
   vis[u]^=1,vis[v]^=1;
   int fa_u=find(u),fa_v=find(v);
   if(fa_v==fa_u){
      ans-=calc(fa_u);
      cnt[fa_u]+=(vis[u]? 1:-1)+(vis[v]? 1:-1);
      ans+=calc(fa_u);
   }else{
      ans-=calc(fa_u)+calc(fa_v);
      cnt[fa_u]+=(vis[u]? 1:-1)+(vis[v]? 1:-1);
      fa[fa_v]=fa_u;
      cnt[fa_u]+=cnt[fa_v];
      ans+=calc(fa_u);
   }
   tag[u]=tag[v]=1;
}

int main(){
   freopen("stroll.in","r",stdin);
   freopen("stroll.out","w",stdout);
   n=read(),m=read();
   for(int i=1;i<=n;i++) fa[i]=i;
   for(int i=1;i<=m;i++) Link(read(),read());
   printf("%d\n",ans); 
   Q=read();
   while(Q--) Link(read(),read()),printf("%d\n",ans);
}
/*
4 3
1 2
2 3
3 4
3
2 4
1 4
1 3
*/