题目描述：

有n个城市，还有m条边（双向），每个城市都有一个发电站，如果一个发电站工作，它能够给它所在的城市和直接相邻的城市提供电力。并且要求每个城市只能由一个发电站来提供电力（即不能够被两个或以上的发电站同时覆盖）。

然后，每个城市的发电站都有一个允许工作时间 ai bj，表示发电站只能在[ai,bi]内的某个连续区间内工作（也可以一个都不选），并且只能选一个区间（即ai = 1, bi = 5, 不能选择1-2 和4-5两个区间）。

然后给你一个数字D，问你能不能安排这n个发电站的工作时间使1~D的时间区间内，每个城市在每个时间都能够被一个发电站覆盖。

可以的话输出任意一种解决方法。

n <= 60, m<= 150, D<=5

解题报告：

初看题意，是一个覆盖问题，n又很小，搜，怎么搜，DLX的精确覆盖模型。

精确覆盖：一个0,1矩阵，选择某些行，使每一列都有且仅有一个1。即用行覆盖列。

行的定义：

一共n * 16行，16就是[1,5]区间的所有小区间：

{{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5},

{2, 2}, {2, 3}, {2, 4}, {2, 5},

{3, 3}, {3, 4}, {3, 5},

{4, 4}, {4, 5},

{5, 5}, {0, 0}};

其中0，0表示不用。

这样第(i – 1) * 16 + j就表示第i个发电站选择小区间j时状态。

(1 <= i <= n, 1 <= j <= 16)

列的定义：

对于第(a – 1) * 16 + b行，一共有n * d + n列。

第(i – 1) * d + j列表示第i个城市的第j天 是否被这一行的状态（a发电站选择b区间）供电，

第n * d + j列为1表示这个覆盖来自第j个发电站（因为每个发电站只能用一次，所以要用额外的n列来限制，和数独那题的解法类似，由于这n列每一列只能被覆盖一次，就限制了使用次数也是1）。

这样图就建好了，套用DLX模板即可。有界的话就输出一个就好了。

代码如下：#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxN = 60 * 20, maxM = 60 * 10;
const int max_size = maxN * maxM;
const int inf = 0x3f3f3f3f;
int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size], RH[max_size];
int S[maxM], O[maxM];
int head, size;
int node(int up, int down, int left, int right) {
    U[size] = up, D[size] = down;
    L[size] = left, R[size] = right;
    D[up] = U[down] = R[left] = L[right] = size;
    return size++;
}
bool mat[maxN][maxM];
void init(int N, int M) {
    size = 0;
    head = node(0, 0, 0, 0);
    for (int j = 1; j <= M; ++j) {
        CH[j] = node(size, size, L[head], head), S[j] = 0;
    }
    for (int i = 1; i <= N; ++i) {
        int row = -1, k;
        for (int j = 1; j <= M; ++j) {
            if (!mat[i][j]) continue;
            if (row == -1) {
                row = node(U[CH[j]], CH[j], size, size);
                RH[row] = i, CH[row] = CH[j], ++S[j];
            } else {
                k = node(U[CH[j]], CH[j], L[row], row);
                RH[k] = i, CH[k] = CH[j], ++S[j];
            }
        }
    }
}
void remove(const int &c) {
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (int i = D[c]; i != c; i = D[i]) {
        for (int j = R[i]; j != i; j = R[j]) {
            U[D[j]] = U[j], D[U[j]] = D[j];
            --S[CH[j]];
        }
    }
}
void resume(const int &c) {
    for (int i = U[c]; i != c; i = U[i]) {
        for (int j = L[i]; j != i; j = L[j]) {
            ++S[CH[j]];
            U[D[j]] = D[U[j]] = j;
        }
    }
    L[R[c]] = R[L[c]] = c;
}
int len;
bool dfs(const int &k) {
    if (R[head] == head) {
        len = k - 1;
        return true;
    }
    int s = inf, c;
    for (int t = R[head]; t != head; t = R[t]) {
        if (S[t] < s) s = S[t], c = t;
    }
    remove(c);
    for (int i = D[c]; i != c; i = D[i]) {
        O[k] = RH[i];
        for (int j = R[i]; j != i; j = R[j]) {
            remove(CH[j]);
        }
        if (dfs(k + 1)) {
            return true;
        }
        for (int j = L[i]; j != i; j = L[j]) {
            resume(CH[j]);
        }
    }
    resume(c);
    return false;
}
int n, m, d;
int move[16][2] = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5},
                         {2, 2}, {2, 3}, {2, 4}, {2, 5},
                                 {3, 3}, {3, 4}, {3, 5},
                                         {4, 4}, {4, 5},
                                                 {5, 5}, {0, 0}};
struct edge{int to, next;}e[20000];
int v[70], cnt, jeo[70][2], ans[70];
void insert(int from, int to)
{
    e[cnt].to = to; e[cnt].next = v[from];
    v[from] = cnt++;
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &d) != EOF)
    {
        memset(v, -1, sizeof(int) * (n + 2)); cnt = 0;
        for(int i = 1; i <= n; i++) insert(i, i);
        while(m--)
        {
            int a, b;scanf("%d%d", &a, &b);
            insert(a, b); insert(b, a);
        }
        memset(mat, 0, sizeof(mat));
        for(int i = 1; i <= n; i++) scanf("%d%d", &jeo[i][0], &jeo[i][1]);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < 15; j++)
            {
                int xx = (i - 1) * 16 + j + 1;
                if (move[j][0] >= jeo[i][0] && move[j][1] <= jeo[i][1])
                {
                    for(int k = v[i]; k != -1; k = e[k].next)
                    {
                        for(int kk = move[j][0]; kk <= move[j][1]; kk++)
                            mat[xx][(e[k].to - 1) * d + kk] = 1;
                    }
                    mat[xx][n * d + i] = 1;
                }
            }
            mat[(i - 1) * 16 + 16][n * d + i] = 1;
        }
        init(n * 16, n * (d + 1));
        dfs(1);
        if (len != n) printf("No solution\n");
        else
        {
            for(int i = 1; i <= len; i++)
            {
                int tmp = ((O[i] - 1) / 16) + 1;
                int tmp2 = O[i] - (tmp - 1) * 16 - 1;
                ans[tmp] = tmp2;
            }
            for(int i = 1; i <= n; i++)
                printf("%d %d\n", move[ans[i]][0], move[ans[i]][1]);
        }
        printf("\n");
    }
    return 0;
}