P3505 [POI2010] TEL-Teleportation

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;
}