题解：AT_arc205_b [ARC205B] Triangle Toggle

· · 题解

分讨后容易发现每次操作不改变某个点相邻白边数量奇偶性。

统计每个点的黑边度数，计算白边度数。

试构造发现一定有办法把某个点的白边两两消除。

于是最少剩余白边数量就是白边度数为奇数的点数的一半。

显然一个边会给整张图的度数带来 2 的贡献，因此是一半。

于是总边数减去白边数就做完了。

#include<bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define mod 998244353
#define int long long
using namespace std;
int read(){
    int sum=0,fish=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')fish=-1,c=getchar();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
int f[200005];
void solve(){
    int n,m;
    cin>>n>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        f[u]++;
        f[v]++;
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        f[i]=n-1-f[i];
        sum+=f[i]&1;
    }
    cout<<(n*(n-1)-sum)/2;
}
signed main(){
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
// 潘丽宝哼笑一声。
//「没有什么骗不骗的。既然是永远不会醒来的梦，那就跟现实没有两样。我为了我们的世界著想，把你从可以和家人团聚的世界拖了出来。我所做的就只有这样而已。」

//「……你还在坚持那种主张啊？」

//「我们奋战的结果顺便救到你们是无所谓，要赋予这件事高尚的意义也是你们的自由。但是，不要把我们牵扯进去。」