国际大学生程序设计竞赛例题_5.21 Turan图

1,题意:
输入:顶点数(n),阶数(k)
要求:图中不能含有任何一个k阶完全图.
输出:图中最多的边数.

2,解决:
将n个顶点尽可能均匀的分成k-1份,在任意两个不属于一个子集的顶点间连边,同一个子集内的顶点之间没有边.

3,实现代码

#include <iostream>
using namespace std;

long group[1000]; //分组

int main()
{
    freopen("5.21.in","r",stdin);
    long n,k;
    long ans; //结果
    int cnt;
    cin>>cnt;
    while(cnt--)
    {
        memset(group,0,sizeof(group));
        ans=0;
        cin>>n>>k;
        if(k>n) cout<<n*(n-1)/2<<endl;
        else
        {
            k--;
            //巧妙的分组实现
            for(int i=0;n;i=(i+1)%k)
            {
                group[i]++;
                n--;
            }
            for(int i=0;i<k;i++)
                for(int j=i+1;j<k;j++)
                    ans+=group[i]*group[j];
            cout<<ans<<endl;
        }

    }
    return 0;
}