網頁

2014年5月8日 星期四

UVa 1194 & POJ 1325 Machine Schedule

題意:
    有A,B兩台機器,A的mode從0~n-1,B的mode從0~m-1,現在有k個job,底下有k行,每行有三個數i,x,y表示第i個job,A機器需用mode(x)完成這項工作,B機器則是需用mode(y),一向工作只需交給A或B其中一個即可。有個規則是A,B這兩台機器變換mode的時候需要restart一次,例如mode(1)變成mode(10)需要restart一次,一開始兩台機器都是從mode(0)開始,問如何分配工作給A或B使得總restart次數最小,並輸出restart次數。

想法:
    一件工作x,y如果選x則不用y,反之選y就不用x,但都是要restart一次,因此可以想到最大匹配數,如果x或y其中一個已經匹配好了,表示A或B其中之一已經restart一次,則這件job就可以跳過。
    具體做法是,將第i個工作x放到左邊那群,y放到右邊那群,並建立(x,y)這條邊,然後套模板求最大匹配數就是答案。注意讀入測資的時候如果x或y其中是0,則直接跳過不用建邊,因為機器從mode(0)開始。


UVa版:
POJ版: