2016级算法期末上机-I.难题·ModricWang's Fight with DDLs III

1126 ModricWang's Fight with DDLs III

思路

由于题目中已经说明了时间经过了正无穷，因此初始位置是不重要的，并且每条边、每个点的地位是均等的。因此到达每个点的概率就是这个点的度数+1（可以停留就等于是有一条连向自己的边），最后的概率就是

\[\frac{\sum S中的点的度数}{\sum 所有点的度数}
\]

时间复杂度\(O(m)\)，空间复杂度\(O(m)\)

代码

#include <iostream>

#include <set>

#include <vector>

#include <iomanip>

using namespace std;

typedef unsigned long long ull;

int main() {

#ifdef ONLINE_JUDGE

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

#endif

    ull n, m, k;

    set<ull> s;

    cin >> n >> m >> k;

    vector<ull> v(n, 1);

    auto tot = n + 2 * m, head = 0;

    for (auto i = 0; i < m; i++) {

        ull a, b;

        cin >> a >> b;

        v[a]++;

        v[b]++;

    }

    for (auto i = 0; i < k; i++) {

        ull p;

        cin >> p;

        head += v[p];

    }

    cout << fixed << setprecision(5) << 1.0 * head / tot << "\n";

}