记录编号	410685	评测结果	AAAAAAAAAA
题目名称	[SGOI] 糊涂的记者	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2017-06-01 20:23:54	内存使用	2.53 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
const int N=510;
int n,m,go[N][N],deg[N],match[N];
db f[N][N],lx[N],ly[N];
bool visx[N],visy[N];
bool cmp(db x){return abs(x)<1e-12;}
bool find(int x){
	visx[x]=1;
	for (int i=0;i<deg[x];i++){
		int v=go[x][i];
		if (!visy[v]&&cmp(lx[x]+ly[v]-f[x][i])){
			visy[v]=1;
			if (!match[v]||find(match[v])){
				match[v]=x;return 1;
			}
		}
	}
	return 0;
}
int main()
{
	freopen("sign.in","r",stdin);
	freopen("sign.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&deg[i]);
		lx[i]=-1e9;
		for (int j=0;j<deg[i];j++){
			scanf("%d",&go[i][j]);
			scanf("%lf",&f[i][j]);
			f[i][j]=log(f[i][j]);
			lx[i]=max(lx[i],f[i][j]);
		}
	}
	for (int i=1;i<=n;i++)
	do{
		for (int i=1;i<=n;i++) visx[i]=visy[i]=0;
		if (find(i)) break;
		db del=1e9;
		for (int v=1;v<=n;v++) if (visx[v])
		for (int i=0;i<deg[v];i++) if (!visy[go[v][i]])
			del=min(del,lx[v]+ly[go[v][i]]-f[v][i]);
		if (cmp(del-1e9)) return puts("NO ANSWER"),0;
		for (int i=1;i<=n;i++)
			if (visx[i]) lx[i]-=del;
		for (int i=1;i<=m;i++)
			if (visy[i]) ly[i]+=del;
	}while (1);
	db ans=1;
	for (int v=1;v<=n;v++)
	for (int i=0;i<deg[v];i++)
		if (match[go[v][i]]==v) ans*=exp(f[v][i]);
	if (ans<1e-12) puts("NO ANSWER");
		else printf("%.4lf\n",ans);
	return 0;
}