某山寨

z4zr的待调教小窝

nyist699 Tunnel 托兰定理

nyist699 Tunnel 托兰定理

Tunnel(托兰定理)
时间限制:1000 ms | 内存限制:65535 KB

描述
有T组数据 每组数据有一个数字n,表示有n个点,问n个点相互连接不构成三角形 最多有几条边?
eg:n=3 A C B 有A----B B----C 所以有2条边 (如果有C----A那么会出现三角型 不可以)

样例输入
2
1
6
样例输出
0
9
来源
SCU Programming Contest 2011 Preliminary

看到这道题 木有思路啊 找规律?。。。水多了就知道找规律了。。。
后来知道了 这事利用了 一个叫托兰定理的东西。

托兰定理:
平面上N个点,至少连(N^2/4)+1条线段必定存在三角形

托兰定理的补形:
平面上N个点,任何三点存在一条直线,至少连N^2-[N^2/4]条线(我不确定。。没试过。。)

add:如果一个n阶简单图,它不包括Kp,则其边数最大值为 (p-2)(n^2-r^2)/(2*(p-1))+r/2 其中r是n mod (p-1)

#include<stdio.h>;
int main(){
    int T,x;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&x);
        printf("%d\n",(x*x)/4);
    }
    return 0;
}

添加新评论

文章二维码