ARC205_B Triangle Toggle
问题陈述
有一个完整的图，图中有 \(n\) 个顶点，编号为 \(1\) 至 \(n\) 。每条边的颜色为黑色或白色。对于 \(i=1,2,\ldots,m\) ，连接顶点 \(U_i\) 和 \(V_i\) 的边被涂成黑色，其他所有的边都被涂成白色。
您可以执行以下操作零次或多次。
- 选择满足 \(1\leq a\leq b\leq c\leq N\) 的整数 \((a,b,c)\) ，并将以下三条边分别重新涂色：白色涂成黑色，黑色涂成白色。
- 连接顶点 \(a\) 和 \(b\) 的边
- 连接顶点 \(b\) 和 \(c\) 的边
- 连接顶点 \(a\) 和 \(c\) 的边
请找出在进行适当操作时最多可以被涂成黑色的边的数量。
[!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\) 。
2. \(n\) 为偶数
同理：新加入的两个顶点与其余的 \(n\) 个顶点都能构成三角形。
但是因为 \(n\) 为偶数，所以两顶点之间的边经过偶数次计算后为白色，
所以增加的黑色边数为 \(2n\) 。
显然: \(f(3)=3,f(4)=4\) 。
整理可得：
其次考虑 \(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;
}
完结撒花！！！
我的博客