http://acm.hdu.edu.cn/showproblem.php?pid=1150

?

題意：有兩臺機器A和B以及N個需要運行的任務。每臺機器有M種不同的模式，而每個任務都恰好在一臺機器上運行。如果它在機器A上運行，則機器A需要設置為模式xi,如果它在機器B上運行，則機器A需要設置為模式y(tǒng)i。每臺機器上的任務可以按照任意順序執(zhí)行，但是每臺機器每轉換一次模式需要重啟一次。請合理為每個任務安排一臺機器并合理安排順序，使得機器重啟次數(shù)盡量少。

C++版本一

題解：

二分圖的最小頂點覆蓋數(shù)=最大匹配數(shù)

本題就是求最小頂點覆蓋數(shù)的。

每個任務建立一條邊。

最小點覆蓋就是求最少的點可以連接到所有的邊。本題就是最小點覆蓋=最大二分匹配數(shù)。

注意一點就是：題目說初始狀態(tài)為0，所以如果一個任務有一點為0的邊不要添加。因為不需要代價。

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; bool vis[N]; bool mp[N][N]; int match[N]; char str; struct node{}; bool dfs(int u){for(int i=0;i<m;i++){if(!vis[i]&&mp[u][i]){vis[i]=1;if(match[i]==-1||dfs(match[i])){match[i]=u;return 1;}}}return 0; } int maxmatch(){int res=0;memset(match,-1,sizeof(match));for(int i=0;i<n;i++){memset(vis,0,sizeof(vis));if(dfs(i))res++;}return res; } void init(){memset(mp,0,sizeof(mp));} int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d",&n)&&n){scanf("%d%d",&m,&k);init();for(int i=1;i<=k;i++){scanf("%d%d%d",&t,&u,&v);if(u&&v)mp[u][v]=1;}cout<<maxmatch()<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

/* HDU 1150 題目大意;有兩臺機器A和B以及N個需要運行的任務。每臺機器有M種不同的模式，而每個任務都恰好在一臺機器上運行。如果它在機器A上運行，則機器A需要設置為模式xi,如果它在機器B上運行，則機器A需要設置為模式y(tǒng)i。每臺機器上的任務可以按照任意順序執(zhí)行，但是每臺機器每轉換一次模式需要重啟一次。請合理為每個任務安排一臺機器并合理安排順序，使得機器重啟次數(shù)盡量少。 二分圖的最小頂點覆蓋數(shù)=最大匹配數(shù)本題就是求最小頂點覆蓋數(shù)的。相當于是最小的點消滅掉所有的邊，所以是最小頂點覆蓋*/#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std;/* ************************************************************************** //二分圖匹配（匈牙利算法的DFS實現(xiàn)） //初始化：g[][]兩邊頂點的劃分情況 //建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配 //g沒有邊相連則初始化為0 //uN是匹配左邊的頂點數(shù)，vN是匹配右邊的頂點數(shù) //調用：res=hungary();輸出最大匹配數(shù) //優(yōu)點：適用于稠密圖，DFS找增廣路，實現(xiàn)簡潔易于理解 //時間復雜度:O(VE) //***************************************************************************/ //頂點編號從0開始的 const int MAXN=110; int uN,vN;//u,v數(shù)目 int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u)//從左邊開始找增廣路徑 {int v;for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增廣路，反向linker[v]=u;return true;}}return false;//這個不要忘了，經(jīng)常忘記這句 } int hungary() {int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res; } //******************************************************************************/ int main() {int k;int i,u,v;while(scanf("%d",&uN),uN){scanf("%d%d",&vN,&k);memset(g,0,sizeof(g));while(k--){scanf("%d%d%d",&i,&u,&v);if(u>0&&v>0)g[u][v]=1;//初始狀態(tài)為0，一開始0的邊不要加}printf("%d\n",hungary());}return 0; }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Machine Schedule的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。