糊涂的记者 解题报告
最佳匹配，要求积最大，我们可以把所有的边权取ln，最后结果再exp，这样就把积最大转化成了和最大，直接用KM算法即可。最终结果输出要求“保留四位有效数字”，不是很容易写出，例如有0.0000000007279这样的答案。没有直接的函数可以按这种要求输出。我的方法是逐位输出，每次乘以10取整，直到遇到5位有效数字，然后根据最后一位判断进位。
/*
* Problem: 糊涂的记者
* Author: Guo Jiabao
* Time: 2009.3.24 21:58
* State: Solved
* Memo: KM算法 对数转换 slack
*/
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=501,MAX=MAXN+MAXM;
const double FINF=1e20,pr=1e-12;
using namespace std;
int N,M,T;
int Match[MAX];
bool vis[MAX];
double adj[MAX][MAX];
double L[MAX],Slack[MAX];
void init()
{
int i,j,c,b;
double v;
freopen("sign.in","r",stdin);
freopen("sign.out","w",stdout);
scanf("%d%d",&N,&M);
T=N+M;
for (i=1;i<=T;i++)
for (j=1;j<=T;j++)
adj[i][j]=-FINF;
for (i=1;i<=N;i++)
{
scanf("%d",&c);
for (j=1;j<=c;j++)
{
scanf("%d%lf",&b,&v);
b+=N;
adj[i][b]=log(v);
}
}
}
inline bool equal(double a,double b)
{
double c=a-b;
c=c<0?-c:c;
return c<pr;
}
bool path(int i)
{
vis[i]=true;
for (int j=N+1;j<=T;j++)
{
double t=L[i]+L[j]-adj[i][j];
if (!vis[j] && equal(t,0))
{
vis[j]=true;
if (Match[j]==0 || path(Match[j]))
{
Match[j]=i;
return true;
}
}
else if (t<Slack[j])
Slack[j]=t;
}
return false;
}
void KM()
{
int i,j,k;
double delta;
for (i=1;i<=N;i++)
{
L[i]=0;
for (j=N+1;j<=T;j++)
if (adj[i][j]>L[i])
L[i]=adj[i][j];
}
for (i=1;i<=N;i++)
{
for(;;)
{
memset(vis,0,sizeof(vis));
for (j=N+1;j<=T;j++)
Slack[j]=FINF;
if (path(i)) break;
delta=FINF;
for (k=N+1;k<=T;k++)
if (!vis[k] && Slack[k]<delta)
delta=Slack[k];
for (j=1;j<=N;j++)
if (vis[j])
L[j]-=delta;
for (j=N+1;j<=T;j++)
if (vis[j])
L[j]+=delta;
}
}
}
void print()
{
int i,b,k,u,c;
double r=0;
int p[100];
for (i=N+1;i<=T;i++)
r+=adj[Match[i]][i];
r=exp(r);
if (r<pr)
printf("NO ANSWER");
else
{
p[0]=0;
for(k=1;;k++)
{
r*=10;
b=(int)r;
if (b==0)
p[k]=0;
else
break;
}
u=k;
for(;k<=u+4;k++)
{
b=(int)r;
p[k]=b;
r=(r-b)*10;
}
--k;
if (p[k]>=5)
p[--k]++;
for (;p[k]==10;k--)
{
p[k]=0;
p[k-1]++;
}
printf("%d.",p[0]);
u=c=0;
if (p[0]==1)
u=c=1;
for (i=1;c<4;i++)
{
if (p[i]>0) u=1;
if (u==1) c++;
printf("%d",p[i]);
}
}
printf("n");
}
int main()
{
init();
KM();
print();
return 0;
}
糊涂的记者
<div class="MainText">
<strong>【问题描述】</strong>
<p class="MsoNormal" align="left">在如今的信息社会中，时间 - 就是生命，对于记者们来说，如何以最快的速度传递消息就显得十分重要了，而为了尽快记录消息内容，速记也是必不可少的。速记就是用一些简单且特殊的符号表示一定的含义，具体如何对应依个人习惯而定，没有一种固定的表示方法。
Tom 是一名报社的新闻记者，常常马不停蹄的跟着新闻跑，有时只能随手记下采访的内容，让人送回报社，而自己又奔赴下一个现场。不过 Tom 是一个糊涂的记者，有时忙中出错，把用自己的速记符号写的内容直接传回报社。因为一时联系不上 Tom ，但这条新闻又十分重要，要赶着在当天的报纸排版前整理出来，于是 Tom 的同事们只好来猜测 Tom 的速记符号的意思。幸运的是 Tom 的同事们与他共事的时间也不短了，对于 Tom 的一些用词情况有一定的了解，经过讨论，他们列出了一张可能性表来表示每一个速记符号可能与哪些单词相对应，并列出了对应的可能性有多大。
你的任务是：根据 Tom 的同事们提供的可能性表，找出一种可能性最大的速记符号与单词的对应方法（可能性应该相乘来计算）。
<strong> 注意 </strong>： <strong>每一个速记符号有且只有一个单词与其对应，每一个单词有不超过一个速记符号与其对应（可能没有速记符号与之对应）。 </strong>
<p class="MsoNormal">【输入格式】</p>
<p class="MsoNormal">文件的第一行有两个整数，分别为速记符号的个数 n(1<=n<=100) 和单词总 m (1<=m<=500) 。
从第 1 行到第 n+1 行为每个速记符号可能对应的单词及其可能性。
第 i+1(1<=i<=n) 行的第一个数 Ci 表示第 i 个速记符号可能与 Ci 个单词相对应，后面有 Ci 个数对 (Nik ， Rik)(1<=k<=Ci) ，表示第 i 个速记符号与第 Nik 个单词相对应的可能性为 Rik （ Rik 为大于 0 小于 1 的实数）。
<p class="MsoNormal">【输出格式】</p>
<p class="MsoNormal">输出文件仅包含一行，若有解则输出一个实数即最大的可能性，保留四位有效数字（四舍五入），若无解则输出 "NO ANSWER" 。
（当可能性大于 1e-12 时才被视为有解）
<p class="MsoNormal">【输入输出样例】</p>
<p class="MsoNormal">输入文件</p>
<p class="MsoNormal">3 3</p>
<p class="MsoNormal">2 1 0.4 3 0.2</p>
<p class="MsoNormal">1 3 0.8</p>
<p class="MsoNormal">3 1 0.1 2 0.9 3 0.2</p>
<p class="MsoNormal">
输出文件
0.2880</div>
上次修改时间 2017-02-03