题解：AT_arc205_b [ARC205B] Triangle Toggle

· · 题解

ARC205_B Triangle Toggle

问题陈述

有一个完整的图，图中有 n 个顶点，编号为 1 至 n 。每条边的颜色为黑色或白色。对于 i=1,2,\ldots,m ，连接顶点 U_i 和 V_i 的边被涂成黑色，其他所有的边都被涂成白色。

您可以执行以下操作零次或多次。

请找出在进行适当操作时最多可以被涂成黑色的边的数量。

[!NOTE]

  • 3\leq n\leq 2\times 10^5
  • 0\leq m\leq 2\times 10^5
  • 1\leq U_i < V_i\leq N
  • (U_i , V_i) \neq (U_j , V_j)$ $(i \neq j)

思路

首先考虑 m=0 时的最优解

1. n 为奇数

当顶点数为 n 时的最优解为 f(n) ，则需由 f(n) 推导 f(n+2) 。

新加入的两个顶点与其余的 n 个顶点都能构成三角形，但是新加入的两顶点之间的边重复计算 n 次。

因为 n 为奇数，所以两顶点之间的边最终为黑色，

所以最后增加的黑色边数为 2n+1 。

f(n+2)=f(n)+2n+1\quad(n为奇数)

2. n 为偶数

同理：新加入的两个顶点与其余的 n 个顶点都能构成三角形。

但是因为 n 为偶数，所以两顶点之间的边经过偶数次计算后为白色，

所以增加的黑色边数为 2n 。

f(n+2)=f(n)+2n\quad (n为偶数)

显然: f(3)=3,f(4)=4 。

整理可得：

f(n)=\frac{n(n-1)}{2}\quad (n为奇数) \\ f(n)=\frac{n(n-2)}{2}\quad (n为偶数)

其次考虑 m\ne 0 的情况

其实就是在 m=0 时的最优解上进行修改

重点来了！！！

对于 𝑛 为奇数来说，每一个顶点已经和剩下的 𝑛−1 个顶点连接一条黑边，

所以每多一条边相连，答案就减一。

但是我们可以通过若干次操作，把一条链式路径化简到一条边（以下称为极简路径），或者把一条环形路径化简为零，从而把损失降到最低。

对于 𝑛 为偶数来说，每一个顶点已经和剩下的 𝑛−1 个顶点中的 n-2 个顶点连接一条黑边，

所以一个顶点最多再与一个顶点连一条黑色的边。

一条环形路径的每一条边对答案都有一个贡献 +1 或 -1 ，

由于每个顶点已经连接 n-2 条黑色边，所以贡献为 +1 的边会使两个顶点处于“满载”情况，

此时无论这两个顶点的另一条边连接到哪，这两条边的贡献都为 -1 ，

所以每一条贡献为 +1 的边的两旁一定为两条贡献为 -1 的边，

显然，环形路径对答案的贡献一定小于等于 0 ，所以需通过若干次操作化简为零；

一条链式路径的每一条边对答案的贡献规律同上，

可以证明总体贡献小于等于 +1 ，

但是可以通过若干次操作获得一条贡献为 +1 的极简路径，

所以一条链式路径对答案的贡献恒为 +1 。

综上所述，我们需要求出极简路径数量，并消除所有环形路径。

赛时代码(AC)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,f[N],sum;
signed main(){
    cin>>n>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        if(f[u]==v&&f[v]==u){
            f[u]=f[v]=0;
        }//消除环
        else if(!f[u]&&!f[v]){
            f[u]=v,f[v]=u;
        }
        else if(!f[u]&&f[v]>0){
            f[u]=f[v];
            f[f[v]]=u;
            f[v]=0;
        }
        else if(!f[v]&&f[u]>0){
            f[v]=f[u];
            f[f[u]]=v;
            f[u]=0;
        }
        else{
            f[f[u]]=f[v];
            f[f[v]]=f[u];
            f[u]=0,f[v]=0;
        }
        //获取极简路径
    }
    for(int i=1;i<=n;i++){
        if(f[i]>0){
            sum++;
        }
    }
    if(n%2==0){
        cout<<n*(n-2)/2+sum/2;
    }
    else{
        cout<<n*(n-1)/2-sum/2;
    }
    //分类计算
    return 0;
}

完结撒花！！！

我的博客