HDU3572任务调度方案（基于最大流的ISAP算法）
发布时间
阅读量：
阅读量
着手进行网络流的学习。初期阶段的学习仍处于较为基础的模仿层面，只能参考高人留下的博客内容。
这道题目其实颇具价值。题目要求对问题进行建模，进而将其转化为网络流的相关问题。通过这道题可以发现，网络流在锻炼思维方面确实具有积极作用。
简单介绍一下建模的思路。
引入一个超级源点以及一个超级汇点。
将每一个工程项目视为一个节点，每一天也作为一个节点。
每个工程项目对应的每一天所拥有的流量为1，因为每天只能安排一台机器完成一个任务单元。
每一天到超级汇点的流量上限为m，这是由于存在m台机器可供使用。
最终需要判断的是，能够流入超级汇点的总流量
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
#define MAXM 400040
#define INF 0x7ffffff
int head[MAXN], dep[MAXN], gap[MAXN], cur[MAXN];
int cnt;
全部评论 (0)
还没有任何评论哟~