Problem G

k-Colouring of a Graph

You are given a simple graph with N nodes and M edges. The graph has the special property that any connected component of size s contains no more than s+2 edges. You are also given two integers k and P. Find the number of k-colourings of the graph, modulo P.

Recall that a simple graph is an undirected graph with no self loops and no repeated edges. A k-colouring of a graph is a way to assign to each node of the graph exactly one of k colours, such that if edge (u,v) is present in the graph, then u and v receive different colors.

Input

The first line of input consists of four integers, N,M,k, and P (1≤N≤50000, 0≤M≤1.5N, 1≤k≤109, 1≤P≤2?109). The next M lines of input each contains a pair of integers A and B (1≤A≤N, 1≤B≤N), describing an edge in the graph connecting nodes A and B.

Output

Output the number of k-colourings of the given graph, modulo P.

Sample Input 1

3 3 2 10000
1 2
2 3
3 1

Sample output 1

0

Sample Input 2

3 3 4 13
1 2
2 3
3 1

Sample output 2

11

題意

N個節(jié)點M條邊的圖著k種顏色（其中M<=N+2),使得每條邊連接的兩個點是不同的顏色，求著色方案的數(shù)量。

這個問題本身是一個NP問題，應該用回溯法來解決。但是網(wǎng)上的這個模板改出來之后TLE，關了輸入輸出流同步之后還是TLE。我猜應該是這種方法寫的...只是需要再優(yōu)化。不然就是某個鬼畜的數(shù)學方法。

下面的超時代碼：用鄰接表c來表示一個無向連通圖G=(V,E)。用整數(shù)1,2,…,m來表示m種不同的顏色。x[i]表示頂點i所著的顏色來，則問題的解向量可以表示為n元組x[1:n]。問題的解空間可表示一棵高度為n+1的完全m叉樹。解空間樹的第i層中每一結點都有m個兒子，每個兒子相應于x[i]的m個可能的著色之一，第n+1層結點均為葉結點。

在回溯算法中，當i>n時，表示算法已搜索至一個葉結點，得到一個新的m著色方案，因此當前已找到的可m著色方案數(shù)sum增1。當i≤n時，當前擴展結點Z是解空間樹中的一個內(nèi)部結點。該結點有x[i]=1,2,…,m。對當前擴展結點Z的每一個兒子結點,由函數(shù)Ok檢查其可行性，并以深度優(yōu)先的方式遞歸地對可行子樹進行搜索，或剪去不可行子樹。

TLE代碼

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

#define ll long long

std::vector <int> c[50010];

ll point_color[5010];
ll cnt = 0;
ll n, m, u, v, g, p;

bool ok(int k) {
    for(int i = 1; i < k; i++){
        std::vector<int>::iterator result = find(c[k].begin( ), c[k].end( ), i); 
        if(!(result == c[k].end()) && point_color[i] == point_color[k]) {
            return 0;
        }
    }
    return 1;
}

void graphcolor(int n, int m) {
    for(int i = 1; i <= n; i++)
        point_color[i] = 0;
    int k = 1;
    while(k >= 1) {
        point_color[k] = point_color[k] + 1;
        while(point_color[k] <= m){
            if (ok(k)) {
                break;
            } else {
                point_color[k]=point_color[k]+1;
            }
        }
        if(point_color[k] <= m && k == n) {         
            cnt++;
            cnt %= p;
        }
        else if(point_color[k] <= m && k < n) {
            k = k + 1;
        } else {
            point_color[k] = 0;
            k = k - 1;
        }
    }
}


int main(int argc, char *argv[]) {
    std::ios::sync_with_stdio(false); 
    std::cin >> n >> g >> m >> p;
    int s, t;
    for(int i=1; i <= g ; i++) {
        std::cin >> s >> t;
        c[s].push_back(t);
        c[t].push_back(s);
    } 
    graphcolor(n, m);
    std::cout << cnt << std::endl;
    return 0;
}