程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu1150 Machine Schedule

hdu1150 Machine Schedule

編輯:關於C++
有兩台機器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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved