Description
https://www.luogu.com.cn/problem/P3505
Solution
水题不会做了,警戒!
题目就是想让我们把一张图分为至少 $6$ 个部分(显然 $6$ 个部分更优),使得每个部分的点只和自己部分以及相邻部分的点有边。
我们直接把第 $1$ 部分设为 $1$ 号点,第 $6$ 部分设为 $2$ 号点,与 $1$ 相邻的点显然要在第 $2$ 部分,与 $2$ 相邻的点要在第 $5$ 部分。
同样的,与第 $2$ 部分相邻的点要在第 $3$ 部分,与第 $5$ 部分相邻的点一定要在第 $4$ 部分。而现在的问题转化为如何分配还没有分配的点,使得边数最多。
令 $d_i$ 表示当前第 $i$ 部分每个部分的点的数量。考虑新加入每个部分的贡献。第 $2,3,4,5$ 部分分别有 $d_2\times d_3,d_2\times d_3\times d_4,d_3\times d_4\times d_5,d_4\times d_5$,显然加入第 $3,4$ 部分的贡献更大的那一个。而且这样贪心是对的,无论加入 $3,4$ 都不会对之后加入的点的贡献比较有变化。
复杂度 $O(n+m)$。
最后统计边数 $-m$ 即可,不需要像其他题解一样容斥很麻烦。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<bits/stdc++.h> #define int long long #define ull unsigned long long #define maxn 40005 #define put() putchar('\n') #define Tp template<typename T> #define Ts template<typename T,typename... Ar> using namespace std; Tp void read(T &x){ int f=1;x=0;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} x*=f; } namespace Debug{ Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;} Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} #define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; #define fi first #define se second #define mk make_pair const int mod=1e9+7; int power(int x,int y=mod-2) { int sum=1; while (y) { if (y&1) sum=sum*x%mod; x=x*x%mod;y>>=1; } return sum; } int n,m; vector<int>to[maxn]; int ans; int d[7],c[maxn]; signed main(void){ int i,j,k,l,x,y; read(n);read(m); for (i=1;i<=m;i++) { read(x),read(y); to[x].push_back(y); to[y].push_back(x); } d[1]++;d[6]++; for (auto y:to[1]) d[2]++,c[y]=2; for (auto y:to[2]) d[5]++,c[y]=5; for (i=3;i<=n;i++) if (!c[i]) { int fl=0; for (auto y:to[i]) { if (c[y]==2) fl=1; else if (c[y]==5) fl=2; } if (fl==1) d[3]++,c[i]=3; else if (fl==2) d[4]++,c[i]=4; else { if (d[2]>d[5]) d[3]++,c[i]=3; else d[4]++,c[i]=4; } } for (i=1;i<=6;i++) ans+=(d[i]*(d[i]-1)/2); for (i=1;i<=5;i++) ans+=d[i]*d[i+1]; printf("%lld\n",ans-m); return 0; }
|