Codeforces 755E：PolandBall and White-Red graph（构造+思维）

http://codeforces.com/contest/755/problem/E

题意：给出n个点和一个距离d，让你在这个n个点的图里面构造一个子图，使得这个子图的直径和补图的直径的较小值为d，如果不可能输出-1，如果可能把子图的边表示出来。

思路：一个图的直径就是图的任意两点之间的距离的最大值。

这里有参考：http://blog.csdn.net/jasonvictoryan/article/details/54572646

感觉这种类型的构造题目不会做的话还是只能找规律，当然这个规律实在挺难的。

其实我们可以发现，要么保证子图的直径 = k或者保证补图的直径 = k即可。

按照这个思路我们可以画多几个图发现：

只有 k = 2 或者 3 的时候才有解。

1、当 k = 2 时，通过样例可以发现，连一条从 1 到 n 的链即可，这样可以保证补图的直径是2。但是当 n <= 4 的时候无解。

2、当 k = 3 时，将 1 和 2, 2 和 3 连边，再将 4 到 n 的点连向 3，这样可以保证子图的直径是3。但是 n <= 3 的时候无解。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
typedef long long LL;

int main() {
    int n, k;
    cin >> n >> k;
    if(k != 2 && k != 3) puts("-1");
    else {
        if(k == 2) {
            if(n <= 4) puts("-1");
            else {
                printf("%d
", n - 1);
                for(int i = 1; i < n; i++) printf("%d %d
", i, i + 1);
            }
        } else {
            if(n <= 3) puts("-1");
            else {
                printf("%d
", n - 1);
                printf("1 2
2 3
");
                for(int i = 4; i <= n; i++) printf("3 %d
", i);
            }
        }
    }
    return 0;
}