建圖：把每個任務(wù)和每一天都看做一個點(diǎn)，添加源點(diǎn)和匯點(diǎn)。源點(diǎn)與每個任務(wù)之間連一條邊，容量為完成該任務(wù)所需處理次數(shù)。若第i個任務(wù)可以在Si至Ei天處理，則由該任務(wù)向這些天分別連一條邊，容量為1，表示此任務(wù)每天只能被處理一次。最后，從每一天連一條到匯點(diǎn)的邊，容量為機(jī)器數(shù)M，表示每天可以處理M個任務(wù)。若求出的最大流等于所有任務(wù)需要處理的次數(shù)之和，說明能完成任務(wù)；否則，不能完成任務(wù)。

AC:

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm>using namespace std;const int maxn = 1111; const int maxm = 505000; const int oo = 1 << 30;int idx; int cur[maxn], pre[maxn]; int dis[maxn], gap[maxn]; int aug[maxn], head[maxn];struct Node {int u, v, w;int next; }edge[maxm];void addEdge(int u, int v, int w) {edge[idx].u = u;edge[idx].v = v;edge[idx].w = w;edge[idx].next = head[u];head[u] = idx++;edge[idx].u = v;edge[idx].v = u;edge[idx].w = 0;edge[idx].next = head[v];head[v] = idx++; }int SAP(int s, int e, int n) {int max_flow = 0, v, u = s;int id, mindis;aug[s] = oo;pre[s] = -1;memset(dis, 0, sizeof(dis));memset(gap, 0, sizeof(gap));gap[0] = n; // 我覺得這一句要不要都行，因?yàn)閐is[e]始終為0for (int i = 0; i <= n; ++i){ // 初始化當(dāng)前弧為第一條弧cur[i] = head[i];}while (dis[s] < n){bool flag = false;if (u == e){max_flow += aug[e];for (v = pre[e]; v != -1; v = pre[v]) // 路徑回溯更新殘留網(wǎng)絡(luò){id = cur[v];edge[id].w -= aug[e];edge[id^1].w += aug[e];aug[v] -= aug[e]; // 修改可增廣量，以后會用到if (edge[id].w == 0) u = v; // 不回退到源點(diǎn)，僅回退到容量為0的弧的弧尾}}for (id = cur[u]; id != -1; id = edge[id].next){ // 從當(dāng)前弧開始查找允許弧v = edge[id].v;if (edge[id].w > 0 && dis[u] == dis[v] + 1) // 找到允許弧{flag = true;pre[v] = u;cur[u] = id;aug[v] = min(aug[u], edge[id].w);u = v;break;}}if (flag == false){if (--gap[dis[u]] == 0) break; /* gap優(yōu)化，層次樹出現(xiàn)斷層則結(jié)束算法 */mindis = n;cur[u] = head[u];for (id = head[u]; id != -1; id = edge[id].next){v = edge[id].v;if (edge[id].w > 0 && dis[v] < mindis){mindis = dis[v];cur[u] = id; // 修改標(biāo)號的同時(shí)修改當(dāng)前弧}}dis[u] = mindis + 1;gap[dis[u]]++;if (u != s) u = pre[u]; // 回溯繼續(xù)尋找允許弧}}return max_flow; }int main() {int t, n, m, pi, si, ei;int Max, sum, source, sink, vn;scanf("%d", &t);for (int cas = 1; cas <= t; ++cas){idx = 0;memset(head, -1, sizeof(head));sum = 0; source = 0; Max = 0;scanf("%d %d", &n, &m);for (int i = 1; i <= n; ++i){scanf("%d %d %d", &pi, &si, &ei);sum += pi;Max = max(Max, ei);addEdge(source, i, pi);for (int j = si; j <= ei; ++j){addEdge(i, n + j, 1);}}sink = n + Max + 1;vn = sink + 1;for (int i = 1; i <= Max; ++i){addEdge(n + i, sink, m);}if (SAP(source, sink, vn) == sum)printf("Case %d: Yes\n\n", cas);else printf("Case %d: No\n\n", cas);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3572（最大流）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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