網頁

2014年6月3日 星期二

UVa 10746 Crime Wave - The Sequel

想法:
    銀行編號1~N,警察編號N+1~N+M,源點S=0以及匯點T=N+M+1。一開始先將S連到每間銀行,每個警察連到T,以及每間銀行連到每個警察,以上單向邊容量都為1。
    接下來就是套模板做MCMF,注意輸出的時候因為是double,因為進位問題所以要把答案加上一個極小的數字,例如,如果printf("%.2f", 17.225);,結果是輸出17.22,因此要printf("%.2f", 17.225+0.000000001);才會是正確答案17.23。