BZOJ 2878 Noi 2012 잃어버린 놀이공원

팁: 1.먼저 폭력 상황을 고려한DP 방정식 2.링 위의 점이 매우 적고, 만약 당신이 링 위에서 걷는 것이 연속적인 한 단락일 뿐이라면, 아마도 DP를 개선할 수 있을 것이다
코드 세부 사항:

#include 
using namespace std;
const int maxn = 1e5+1e2;

int n , m;
struct edge { int t , v , re; edge(int t=0 , int v=0 , int re=0):t(t),v(v),re(re){} };

vector g[maxn];
vector<vector<double> > d[maxn];

bool vis[maxn] , inCircle[maxn]; 
int pre[maxn] , cnt , dic[maxn] , redic[maxn];;
bool dfs(int x)
{
    vis[x] = 1;
    for(int i=0;iif(e.t == pre[x]) continue;

        if(vis[e.t])
        {
            while(true)
            {
                dic[++cnt] = x;
                redic[x] = cnt;
                inCircle[x] = 1;
                if(x == e.t) break;
                x = pre[x];
            }
            return true;
        }
        pre[e.t] = x;
        if(dfs(e.t)) return true;
    }
    return false;
}

double dp(int x , int n1 , int n2)
{
    double &res = d[x][n1][n2];
    if(res > -1) return res;

    res = 0;
    int cnt = 0;
    for(int i=0;iif(i != n1)
    {
        edge& e = g[x][i];
        if(e.t == dic[n2]) continue;

        ++cnt;
        res += e.v;
        if(inCircle[x] == inCircle[e.t]) res += dp(e.t , e.re , n2);
        else if(inCircle[x] && !inCircle[e.t]) res += dp(e.t , e.re , 0);
        else if(!inCircle[x] && inCircle[e.t]) res += dp(e.t , e.re , redic[e.t]);
    }

    if(!cnt) return 0;
    return res /= cnt;
}

int main(int argc, char *argv[]) {
    #ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    #endif

    cin>>n>>m;
    for(int i=1 , s , t , v;i<=m;i++)
    {
        scanf("%d%d%d" ,&s , &t , &v);
        assert(s != t);
        g[s].push_back(edge(t , v , g[t].size()));
        g[t].push_back(edge(s , v , g[s].size()-1));
    }

    dfs(1);

    for(int i=1;i<=n;i++)
    {
        d[i].resize(g[i].size() + 1);
        for(int j=0;j<=g[i].size();j++) 
        {
            d[i][j].resize(cnt + 1);
            for(int k=0;k<=cnt;k++) d[i][j][k] = -100;
        }
    }

    double res = 0;
    for(int i=1;i<=n;i++) if(inCircle[i]) res += dp(i , g[i].size() , redic[i]); else res += dp(i , g[i].size() , 0);

    res /= n;
    printf("%.5lf
" , res);
    return 0;
}

DP 방정식: di, j, k가 i번째 점까지 가면 이때의 j번째 변도 갈 수 없고 링의 k번째 점의 기대 거리도 갈 수 없다.
만약에 우리가 나무의 상황만 고려한다면 앞의 두 상태는 Okay이다. 이때 고리가 있을 수 있기 때문에 우리는 모든 경로가 처음으로 고리에 들어간 그 노드가 누구인지 기록해야 한다. 왜냐하면 우리는 그것을 돌아갈 수 없기 때문이다.
최적화된 전략은 링을 빠져나온 후에 3차원이 0이 되도록 강제하는 것이다.
그러나 세심한 독자들은 시간을 초과할 수 있는 방법이라는 것을 알게 될 것이다. 국화도에서 이동하는 시간의 복잡도는 O(이 노드의 변수)이기 때문에 O(n2)로 퇴화할 수 있다.그러나 이 문제의 데이터는 카국화도에 무심하여 이 알고리즘의 운행 시간이 양호하다.