傳送門(mén)

作業(yè)調(diào)度，這道題還真沒(méi)想到能用網(wǎng)絡(luò)流。。。。乍一看跟背包問(wèn)題差不多。
有N個(gè)作業(yè)，M個(gè)機(jī)器，每個(gè)作業(yè)給你一個(gè)耗費(fèi)時(shí)間（時(shí)間段）以及最早開(kāi)始時(shí)間和最晚完成時(shí)間（這兩個(gè)是時(shí)間點(diǎn)），單位是天。一個(gè)作業(yè)同時(shí)只能被一個(gè)機(jī)器做，一個(gè)機(jī)器同時(shí)也只能做一個(gè)作業(yè)，但是，可以只做一部分，之后可以切換別的機(jī)器做。一部分指的是整數(shù)天。

畫(huà)個(gè)圖。把數(shù)據(jù)處理成上面這個(gè)圖，然后按照最大流求解就ojbk了，看看最后的最大流是不是P1+P2+P3+...+PN（最大流必然小于等于這個(gè)，因?yàn)閺脑袋c(diǎn)輸出就這么些）
源點(diǎn)輸出到每個(gè)作業(yè)，權(quán)值等于這個(gè)作業(yè)的耗費(fèi)時(shí)間P，代表你這個(gè)作業(yè)要處理P次（每次1天）；然后的N+1,N+2這些代表具體的某一天（整體上不一定連續(xù)每天都有，要根據(jù)每個(gè)作業(yè)的上下限來(lái)定），比如第一個(gè)作業(yè)的上下限是[N+1,N+3]，那么就把這個(gè)作業(yè)和這個(gè)上下限內(nèi)的每一天都連上一條邊，權(quán)值是1（此時(shí)不用關(guān)心這個(gè)作業(yè)的花費(fèi)時(shí)間，因?yàn)榍懊鎻脑袋c(diǎn)連的邊已限制這一點(diǎn)），權(quán)值是1表示某一天內(nèi)只能處理這個(gè)作業(yè)1天的完成量（這不是廢話么）；然后，代表某一天的每個(gè)點(diǎn)都要和匯點(diǎn)連上一條權(quán)值為M的邊，代表這一天最多能同時(shí)處理M個(gè)作業(yè)（因?yàn)闄C(jī)器只有M個(gè)）。
這個(gè)圖并不關(guān)心某個(gè)作業(yè)被具體哪些機(jī)器處理，因?yàn)檫@個(gè)不重要。只關(guān)心某個(gè)作業(yè)必須在哪些天內(nèi)被處理，以及某一天最多同時(shí)處理多少個(gè)作業(yè)。

這個(gè)題還有個(gè)問(wèn)題，就是他沒(méi)說(shuō)清楚P<=E-S還是P<=E-S+1。這關(guān)系到在上面的圖中某個(gè)作業(yè)要連接E-S個(gè)點(diǎn)還是E-S+1個(gè)點(diǎn)。
當(dāng)然，在樣例中的第二個(gè)輸出為Yes說(shuō)明了是后者。但是真的夠sb的。

【19.3.18 想法】今天結(jié)合HDU 2883這個(gè)題，突然想到一個(gè)問(wèn)題：該方法怎么保證某機(jī)器某一天一定處理某任務(wù)1天的工作量？而不是0.5個(gè)工作量？（也就是說(shuō)從某任務(wù)點(diǎn)到某天數(shù)點(diǎn)的流量會(huì)不會(huì)大于0小于1？）
答案是不會(huì)的，因?yàn)镻_N、M這些值都是整數(shù)且大于等于1，考慮最大流算法尋找增廣路的過(guò)程，權(quán)值為1的邊肯定是整條路上權(quán)值最小的邊，這條路的流量不可能比1再小了。

dinic

#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <string> #include <queue> using namespace std;const int MAX = 500 + 500 + 2 + 10; const int INF = 1e9; int N, M, T; int flow; int sum;struct Edge {int f, t, flow, cap; }; vector<Edge> ve; vector<int> v[MAX];int P, S, E; bool vis[MAX]; int level[MAX]; int cur[MAX];void addEdge(int from, int to, int weight) {ve.push_back(Edge{ from,to,0,weight });ve.push_back(Edge{ to,from,0,0 });v[from].push_back(ve.size() - 2);v[to].push_back(ve.size() - 1); }void init() {ve.clear();for (int i = 0; i <= N + 500 + 1; i++)v[i].clear();flow = sum = 0;memset(vis, 0, sizeof vis); }bool bfs(int t) {memset(level, -1, sizeof level);queue<int> q;q.push(0);level[0] = 0;for (; !q.empty();){int x = q.front();q.pop();for (int i = 0; i < v[x].size(); i++){Edge &e = ve[v[x][i]];if (level[e.t] < 0 && e.flow < e.cap){level[e.t] = level[x] + 1;q.push(e.t);}}}return level[t] >= 0; }int dfs(int n, int t, int f) {if(n == t || f == 0) return f; //for (int& i = cur[n]; i < v[n].size(); i++){Edge& e = ve[v[n][i]];int f0;if (level[e.t] == level[n] + 1 && (f0 = dfs(e.t, t, min(f, e.cap - e.flow))) > 0){e.flow += f0;ve[v[n][i] ^ 1].flow -= f0;return f0;}}return 0; }int main() {scanf("%d", &T);for (int cnt = 1; cnt <= T; cnt++){scanf("%d%d", &N, &M);init();for (int i = 1; i <= N; i++){scanf("%d%d%d", &P, &S, &E);if (P > E - S + 1) //{printf("Case %d: No\n\n", cnt);return 0;}addEdge(0, i, P);for (int j = S; j <= E; j++){addEdge(i, j + N, 1);//addEdge(j + N, 500 + N + 1, M);vis[j + N] = true;}sum += P;}for (int i = N + 1; i <= N + 500; i++)if (vis[i])addEdge(i, N + 500 + 1, M);for (; bfs(N + 500 + 1);){memset(cur, 0, sizeof cur);int temp;for (; temp = dfs(0, N + 500 + 1, INF);)flow += temp;//cout << flow;}printf("Case %d: %s\n\n", cnt, flow == sum ? "Yes" : "No");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/CrossingOver/p/10704876.html

總結(jié)

以上是生活随笔為你收集整理的HDU 3572 Task Schedule的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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