hdu1150 Machine Schedule
有兩台機器A和B以及N個需要運行的任務。每台機器有M種不同的模式，而每個任務都恰好在一台機器上運行。如果它在機器A上運行，則機器A需要設置為模式xi,如果它在機器B上運行，則機器A需要設置為模式yi。每台機器上的任務可以按照任意順序執行，但是每台機器每轉換一次模式需要重啟一次。請合理為每個任務安排一台機器並合理安排順序，使得機器重啟次數盡量少。
二分圖的最小頂點覆蓋數=最大匹配數
本題就是求最小頂點覆蓋數的。
每個任務建立一條邊。
最小點覆蓋就是求最少的點可以連接到所有的邊。本題就是最小點覆蓋=最大二分匹配數。
注意一點就是：題目說初始狀態為0，所以如果一個任務有一點為0的邊不要添加。因為不需要代價
#include
#include
#include
#include
using namespace std;
const int MAXN = 110;
int uN,vN;
int g[MAXN][MAXN];
int linker[MAXN];
bool used[MAXN];
bool dfs(int u){
int v;
for(v=0;v0&&v>0) g[u][v]=1;
}
printf("%d\n",hungary());
}
return 0;
}
