题解归档 - cf113D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf113D
• 本地来源：problems/cf113D/idea.md
• 题目链接：https://codeforces.com/contest/113/problem/D
• 原始标题：CF113D Museum

思路

CF113D Museum

题意

连通无向图 (n\le 22) 个房间，两人在房间 (a,b) 同时随机游走：在房间 (i) 以概率 (p_i) 不动，否则均匀走向相邻房间。走廊不能相遇，只有同一时刻同在同一房间算会合。求在每个房间会合的概率。

Catalog 备注

catalog_priority.json 中本题标注为「二分图匹配 / König」，与真实题面 Museum（随机游走 + 线性方程组） 不符；lib_target 二分图模板应另选 Catalog 题补齐，本题不沉淀匹配模板。

思路

• 状态 ((x,y))：两人分别在 (x,y)。非对角状态 ((x,y),x\ne y) 共 (n^2-n) 个，列变量先排这些，再排 (n) 个对角 ((i,i))（在各点会合的「吸收」贡献）。
• 对每个非对角 ((i,j)) 列方程
  [
  f(i,j)=\sum_{\text{一步转移}} \Pr\cdot f(\text{新状态})
  ]
  移项得系数矩阵一行；对角列出现在转移落到 ((k,k)) 的项里。
• 从起点行 row[a][b] 高斯消元后，在房间 (i) 会合的概率为
  (-A\text{st} / A\text{st})。
• (a=b) 特判：只在房间 (a) 概率为 1。

期望为 0/1 变量时等于概率；复杂度 (O(n^6))，(n\le 22) 可过。

实现要点

• 转移：每人「留」或「走向某一邻居」，枚举 (0\ldots deg)（多的一项表示留在当前点）。
• 列编号：非对角紧凑 (1\ldots n^2-n)，对角 (n^2-n+1\ldots n^2)。
• 用 long double 消元，输出 fixed 10 位。

验证

• 样例 1/2 手对。
• stress.py cf113D -n 500 与 brute.cpp 一致。

代码

来源：problems/cf113D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 12:30:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=25;
const long double eps=1e-12l;
vector<ll>g[maxn];
long double p[maxn],a[maxn*maxn+5][maxn*maxn+5];
ll col[maxn][maxn],row[maxn][maxn],deg[maxn],n,m,sa,sb,i,j,u,v,cnt,tot;
void add(ll r,ll c,long double w){
    if(fabsl(w)<eps) return;
    a[r][c]+=w;
}
void gauss(ll r,ll c){
    ll i,j,k,t;
    for(i=1,k=1;i<=randk<=c;i++){
        t=i;
        for(j=i+1;j<=r;j++) if(fabsl(a[j][k])>fabsl(a[t][k])) t=j;
        if(fabsl(a[t][k])<eps){k++;i--;continue;}
        if(t!=i) for(j=1;j<=c;j++) swap(a[t][j],a[i][j]);
        for(j=1;j<=r;j++) if(j!=i and fabsl(a[j][k])>eps){
            long double zc=a[j][k]/a[i][k];
            for(t=1;t<=c;t++) a[j][t]-=a[i][t]*zc;
        }
        k++;
    }
}
int main(){
    cin>>n>>m>>sa>>sb;
    for(i=1;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1;i<=n;i++){
        cin>>p[i];
        deg[i]=g[i].size();
    }
    if(sa==sb){
        for(i=1;i<=n;i++){
            if(i>1) cout<<" ";
            cout<<fixed<<setprecision(10)<<(i==sa?1.0:0.0);
        }
        cout<<"\n";
        return 0;
    }
    cnt=0;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) col[i][j]=++cnt;
    tot=cnt;
    for(i=1;i<=n;i++) col[i][i]=++tot;
    cnt=0;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) row[i][j]=++cnt;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j){
        ll r=row[i][j];
        for(llx=0;x<=deg[i];x++){
            for(lly=0;y<=deg[j];y++){
                ll ni=x<(ll)g[i].size()?g[i][x]:i;
                ll nj=y<(ll)g[j].size()?g[j][y]:j;
                long double wi=x<(ll)g[i].size()?(1-p[i])/deg[i]:p[i];
                long double wj=y<(ll)g[j].size()?(1-p[j])/deg[j]:p[j];
                add(r,col[ni][nj],wi*wj);
            }
        }
        add(r,col[i][j],-1);
    }
    gauss(cnt,tot);
    ll st=row[sa][sb];
    for(i=1;i<=n;i++){
        if(i>1) cout<<" ";
        cout<<fixed<<setprecision(10)<<(double)(-a[st][col[i][i]]/a[st][col[sa][sb]]);
    }
    cout<<"\n";
    return 0;
}