记录编号	46467	评测结果	AAAAAAAAAA
题目名称	[SGOI] 糊涂的记者	最终得分	100
用户昵称	怡红公子	是否通过	通过
代码语言	C++	运行时间	0.070 s
提交时间	2012-10-28 00:45:38	内存使用	3.56 MiB

#include<iostream>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<cstring>
using namespace std;
//ifstream fin("cin.in");

int n,m;
double w[105][505]={0};

double lx[105]={0},ly[505]={0},ans=0;
bool vx[105]={0},vy[505]={0};
int f[505]={0};

int Find(int k){
    vx[k]=1;
    for(int i=1;i<=m;++i)
    if(!vy[i]&&lx[k]+ly[i]+0.0000000001>=w[k][i]&&lx[k]+ly[i]-0.0000000001<=w[k][i])
    {
      vy[i]=1;
      if(f[i]==0||Find(f[i]))
      {f[i]=k;return 1;}             
                                    }
    return 0;
    
    }

void KM(){
     for(int i=1;i<=n;++i)
     {
       lx[i]=-1000000000;
       for(int j=1;j<=m;++j)
       if(lx[i]<w[i][j]&&w[i][j]<0) lx[i]=w[i][j];    
             }
     
     for(int i=1;i<=n;++i)
     {
       while(1)
       {
         memset(vx,0,sizeof(vx));
         memset(vy,0,sizeof(vy));
       
         if(Find(i)) break;
         
         double mi=10000000;
         for(int j=1;j<=n;++j)
         if(vx[j])
         for(int k=1;k<=m;++k)
         if(!vy[k]&&w[j][k]<0)               
         if(mi>lx[j]+ly[k]-w[j][k]) 
         mi=lx[j]+ly[k]-w[j][k];
         
         if(mi==10000000) break;

         for(int j=1;j<=n;++j)
         if(vx[j]) lx[j]-=mi;
         for(int j=1;j<=m;++j)
         if(vy[j]) ly[j]+=mi;     
               }    
             }
     for(int i=1;i<=m;++i)
     if(f[i]>0) ans+=w[f[i]][i];
     }

int main()
{
    freopen("sign.in","r",stdin);
    freopen("sign.out","w",stdout);
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;++i)
    {
      int a,b;double s;
      scanf("%d",&a);
      for(int j=1;j<=a;++j)
      {scanf("%d",&b);scanf("%lf",&s);w[i][b]=log(s)/log(10);}
            }
    
    KM();
    
    ans=pow(10,ans);
    if(ans<1e-12) {printf("NO ANSWER\n");return 0;}
    cout<<setprecision(4)<<ans<<endl;//printf("%f\n",ans);
   // system("pause");
    return 0;
    
    }