糊塗的記者解題報告

最佳匹配，要求積最大，我們可以把所有的邊權取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&lt;=n&lt;=100) 和單詞總 m (1&lt;=m&lt;=500) 。
從第 1 行到第 n+1 行爲每個速記符號可能對應的單詞及其可能性。
第 i+1(1&lt;=i&lt;=n) 行的第一個數 Ci 表示第 i 個速記符號可能與 Ci 個單詞相對應，後面有 Ci 個數對 (Nik ， Rik)(1&lt;=k&lt;=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>

相關日誌