题目链接：hdu_5874_Friends and Enemies

题意: 有nn个人, mm种颜色的石头, 人两两之间要么是朋友, 要么是敌人. 每个人可以携带若干种石头或者不带, 要求朋友之间至少携带一种颜色相同的石头, 敌人之间不能携带有相同颜色的石头. 问最坏情况下, mm种颜色是否够.

题解：（叉姐）

Nero搞出了一个结论: nn个点的图, 要求有尽量多的边, 并且不存在三元环. 这个边数就是mm的下界.

对于一个nn个结点的没有三元环的图, 边数最大的就是完全二分图. 于是答案就是((n+1)/2)*(n/2)


1 #include<cstdio>2 3 int main()4 {5     long long n,m;6     while(~scanf("%lld%lld",&n,&m))puts(((n+1)/2)*(n/2)<=m?"T":"F");7     return 0;8 }

View Code

hdu_5874_Friends and Enemies(公式题)