最大割

solution

100分

待我学完线性基.

开锁

solution

100分

每个点只有一条出边和入边,显然图由很多个环组成.
每个环中必须选出一个点,才能打开所有的箱子.
预处理出每个环的大小,设共\(m\)个,大小为\(g_i\).
\(f[i][j]\)表示前\(i\)个环选了\(j\)个点合法的方案数.
\(f[i][j]=\sum_{l=1}^{g_i}f[i-1][j-l]\times{C_{g_i}^l}\)

\(ans=\frac{f[m][k]}{C_n^k}\).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 305
#define max(a,b) a>b?a:b
#define min(a,b) a=1;--l)
					f[i][j]+=f[i-1][j-l]*c[g[i]][l];
		}
		printf("%.6lf\n",f[cnt][k]/c[n][k]);
	}
}
int main(){
	freopen("unlock.in","r",stdin);
	freopen("unlock.out","w",stdout);
	Aireen();
	fclose(stdin);
	fclose(stdout);
	return 0;
}