T1

显然可以打记忆化搜索，搜出每个结局并且在回退时选择时间线。

时间复杂度：\(O(n^3 2^n)\)

空间也是 $ O(n^3 2^n)\(

必须记录 ：当前轮\)O(n)\(，选择人\)O(n)\(，存活态\)O(2^n)\(，每人期望\)O(n)$

考虑优化空间

记搜顺序：轮；状态，顺序决策人,kill的人。转移时存期望。

(状态，顺序决策人先后不冲突，冲突continue);

自下而上循环就是DP

DP枚举：倒序轮,倒序决策人，状态，kill的人

判断决策kill不kill，算上kill不掉的可能

取决策人最优时间线转移（相差<=1e-10时累加状态,cnt++，最后除cnt）

#includeusing namespace std;
const int N=17;
typedef double db;
typedef unsigned int ui;
db p[N];
int n,r;
db mp[2][1<<16][N];
db bstv[N],mst,cand[N];
db eps=1e-10;
int cntt;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// freopen("gunfire.in","r",stdin);// freopen("gunfire.out","w",stdout);cin>>n>>r;bool f=0;for(int i=1;i<=n;i++){cin>>p[i];if(p[i]>0&&i>1){f=1;}}if(n==1){cout<<"1.000000";return 0;}int m=(1<>(j-1))&1){mp[1][i][j]=1.0/tot;}}}int f1=0,f2=1;for(int k=1;k<=r;k++){for(int st=n;st>=1;st--){for(int mask=1;mask<=m;mask++){int cnt=__builtin_popcount(mask);if(cnt==1){int a=__builtin_ctz(mask)+1;for(int k=1;k<=n;k++){mp[f1][mask][k]=0.0;}mp[f1][mask][a]=1.0;continue;}if(!((mask>>(st-1))&1)){for(int k=1;k<=n;k++){mp[f1][mask][k]=mp[f2][mask][k];}continue;}mst=mp[f2][mask][st];for(int i=1;i<=n;i++){bstv[i]=mp[f2][mask][i];}cntt=1;for(int en=1;en<=n;en++){if(en==st) continue;if(!((mask>>(en-1))&1)) continue;int nmask=mask^(1<<(en-1));for(int k=1;k<=n;k++){cand[k]=p[st]*mp[f2][nmask][k]+(1.0-p[st])*mp[f2][mask][k];}db v=cand[st];if(v>mst+eps){for(int k=1;k<=n;k++){bstv[k]=cand[k];}mst=v;cntt=1;} else if(fabs(v-mst)<=eps){for(int k=1;k<=n;k++) bstv[k]+=cand[k];cntt++;}}if(cntt>1){for(int k=1;k<=n;k++){bstv[k]/=cntt;}}for(int k=1;k<=n;k++){mp[f1][mask][k]=bstv[k];}}swap(f1,f2);}}printf("%.6f",mp[f2][m][1]);return 0;
}

删除最少边，成为仙人掌图

显然，有 边数=点数+环数-1

要求删边最小，就要环最多

考虑 DP

\(dp[s]\)表示点集为S的图中最多环

\(O(n 2^n)\)预处理出以点集+连边组成的图有无互不冲突的环(bfs+出入度==2)

在\(s\)和\(t\)交集<=1,即可转移

\(dp[s|t]=max(dp[s|t],dp[t]+1)\)

剪树卡过去

#include
using namespace std;
const int N=20;
typedef unsigned int ui;
int n,m;
ui adj[N];
signed char dp[1<<20];
vectorcyc;inline int pc(ui x){return __builtin_popcount(x);
}inline ui comp(ui s){ui seen=s&-s,front=seen;while(front){ui nxt=0;while(front){int v=__builtin_ctz(front); front&=front-1;nxt|=adj[v];}front=nxt&s&~seen; seen|=front;}return seen;
}
int dfs(ui s){if(dp[s]!=-1)return dp[s];ui core=s,todo=s;while(todo){int v=__builtin_ctz(todo); ui bit=1u<ans)ans=val;if(ans==up)return dp[s]=ans;}}return dp[s]=ans;
}inline void solve(){cin>>n>>m;fill(adj,adj+n,0);int x,y;for(int i=0;i>x>>y;--x;--y;adj[x]|=1u<>c>>_;while(_--){solve();}return 0;
}