程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LightOJ1287

LightOJ1287

編輯：關於C++

Last night you robbed a bank but couldn’t escape and when you just got outside today, the police started chasing you. The city, where you live in, consists of some junctions which are connected by some bidirectional roads.

Since police is behind, you have nothing to do but to run. You don’t know whether you would get caught or not, but if it is so, you want to run as long as you can. But the major problem is that if you leave a junction, next time you can’t come to this junction, because a group of police wait there for you as soon as you left it, while some other keep chasing you.

That’s why you have made a plan to fool the police as longer time as possible. The plan is, from your current junction, you first find the number of junctions which are safe (no police are there) and if you go to one of them; you are still able to visit all the safe junctions (in any order) maintaining the above restrictions. You named them ‘Elected Junction’ or EJ. If there is no such junction; you stop running, because you lose your mind thinking what to do, and the police catch you immediately.

But if there is at least one EJ, you can either fool around the police by staying in the current junction for 5 minutes (actually you just hide there, so the police lose your track thinking which road you might have taken), or you can choose to go to any EJ. The probability of choosing to stay in the current junction or to go to each of the EJ is equal. For example, from the current junction you can go to three EJs, that means the probability of staying in the current junction is 1/4 or the probability to go to any of the EJ is 1/4 since you have four options (either stay in the current junction or go to any of the three junctions).

You can fool the police (by hiding) multiple times in a city, but of course the above conditions should be satisfied. And you have decided not to stop in the middle of any road, because you have the fear that, if you stop in the middle of any road, then the police would surround you from both ends.

Now, given the map of the city and the required time for you to travel in each road of the map; you have to find the expected time for the police to catch you.
Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers n (1 ≤ n ≤ 15) denoting the number of junctions and m, denoting the number of roads in the city. The junctions are numbered from 0 to n - 1.

Each of the next m lines contains three integers u v w (0 ≤ u, v < n, 0 < w ≤ 100, u ≠ v) meaning that there is a road between junction u and v and you need w minutes to travel in the road. Your home is in junction 0 and you are initially in your home. And you may safely assume that there can be at most one road between a pair of junctions.
Output

For each case, print the case number and the expected time in minutes. Errors less than 10-6 will be ignored.
Sample Input

Output for Sample Input

3 2

0 1 3

1 2 3

4 6

0 1 75

0 2 86

0 3 4

1 2 1

1 3 53

2 3 10

5 5

0 1 10

1 2 20

2 3 30

1 3 20

3 4 10

Case 1: 16

Case 2: 106.8333333333

Case 3: 90
Note

For the 3rd case, initially you are in junction 0, and you can either stay here for 5 minutes, or you can move to 1. The probability of staying in 0 is 0.5 and the probability of going to junction 1 is also 0.5. Now if you are in junction 1, either you can stay here for 5 minutes or you can move to junction 2. From junction 1, you cannot move to junction 3, because if you go to junction 3, you can move to junction 2 or junction 4, but if you go to 2, you cannot visit junction 4 (since police would have occupied junction 3), and if you go to junction 4 from 3, you cannot visit junction 2 for the same reason. So, from 1, junction 2 is the only EJ, but junction 3 is not.

給你一張無向圖,從0出發,每次都先觀察,從當前點走到下一個點,如果從那個點開始可以遍歷完全部的點,那麼這個點成為EJ
如果EJ個數為0,不行動
否則,可以選擇在往任意一個EJ走,還可以先在原地停留5分鐘
概率都相同,求遍歷完圖的期望時間

很明顯的概率dp
dp[u][sta]表示當前在點u,走過的點的狀態為sta時,遍歷完圖的期望時間
至於那個EJ點個數判斷,可以事先dfs下來然後保存好,注意也要記憶化搜索

    /*************************************************************************
        > File Name: K.cpp
        > Author: ALex
        > Mail: [email protected]
        > Created Time: 2015年05月18日 星期一 18時29分15秒
     ************************************************************************/

    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include
    #include 
    #include 
    #include 

    using namespace std;

    const double pi = acos(-1.0);
    const int inf = 0x3f3f3f3f;
    const double eps = 1e-15;
    typedef long long LL;
    typedef pair  PLL;

    vector  roads[20];
    int n;
    double dp[16][(1 << 15) + 10];
    int ok[16][(1 << 15) + 10];

    double DP(int u, int sta) {
        double &res = dp[u][sta];
        if (res != -1.0) {
            return res;
        }
        int cnt = 0;
        int size = roads[u].size();
        for (int i = 0; i < size; ++i) {
            int v = roads[u][i].first;
            if (sta & (1 << v)) {
                continue;
            }
            if (ok[v][sta | (1 << u)] == 1) {
                ++cnt;
            }
        }
        if (!cnt) {
            return res = 0;
        }
        res = 0;
        double p = 1.0 / (1 + cnt);
        for (int i = 0; i < size; ++i) {
            int v = roads[u][i].first;
            if (sta & (1 << v)) {
                continue;
            }
            if (!ok[v][sta | (1 << u)]) {
                continue;
            }
            int w = roads[u][i].second;
            res += p * w + p * DP(v, sta | (1 << u));
        }
        res += 5.0 * p;
        res /= (1 - p);
        return res;
    }

    void dfs(int u, int sta) {
        if ((sta | (1 << u)) == (1 << n) - 1) {
            ok[u][sta] = 1;
            dp[u][sta] = 0;
            return;
        }
        ok[u][sta] = 0;
        int size = roads[u].size();
        for (int i = 0; i < size; ++i) {
            int v = roads[u][i].first;
            if (!(sta & (1 << v))) {
                if (ok[v][sta | (1 << u)] == -1) {
                    dfs(v, sta | (1 << u));
                }
                ok[u][sta] = (ok[u][sta] || ok[v][sta | (1 << u)]);
            }  
        }
    }

    int main() {
        int t, icase = 1;
        scanf("%d", &t);
        while (t--) {
            int m;
            scanf("%d%d", &n, &m);
            for (int i = 0; i < n; ++i) {
                roads[i].clear();
            }
            int u, v, w;
            for (int i = 0; i < m; ++i) {
                scanf("%d%d%d", &u, &v, &w);
                roads[u].push_back(make_pair(v, w));
                roads[v].push_back(make_pair(u, w));
            }
            for (int i = 0; i < (1 << n); ++i) {
                for (int j = 0; j < n; ++j) {
                    dp[j][i] = -1.0;
                    ok[j][i] = -1;
                }
            }
            dfs(0, 0);
            printf("Case %d: %.12f\n", icase++, DP(0, 0));
        }
        return 0;
    }