首页 > 代码库 > HDU 3572 Task Schedule(ISAP)
HDU 3572 Task Schedule(ISAP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3572
题意:m台机器,需要做n个任务。第i个任务,你需要使用机器Pi天,且这个任务要在[Si , Ei]区间内完成才有效。对于一个任务,只能由一个机器来完成,一个机器同一时间只能做一个任务。当然,一个任务可以分成几段不连续的时间来完成。问,能否做完全部任务。
题意很清晰,也就是判断是否是满流。
对于网络流问题,模板大家都有,关键在于如何建图(详见资料)
思路:今天问了龙哥,对建图有了一定的了解,建图分为4部分,源点->X集合->Y集合->汇点(X、Y类似于二分匹配图),确定这个4个部分后,就是找这个4个部分的关系,也就是构建容量网络
这题的X集合可以当做任务编号,Y集合当做天数(第几天)
某任务->某一天,若是可以在这天做任务,建一条容量为1的边,最后,把每天到汇点再建一条边容量M(表示每台机器最多工作M个任务)即最大容量是M。
以第二组实例作图(真挫。。)
模板应用的是ISAP(可当做模板),个人很倾向ISAP
Accepted | 2292 KB | 62 ms | C++ |
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #include <queue> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 1100; const int maxm = 400000; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b #define MAX INT_MAX int head[maxn], sum, bnum; int dis[maxn]; //残量网络中节点 i 到汇点 t 的最短距离 int num[maxn]; //和 t 的最短距离等于 i 的节点数量 int cur[maxn]; //当前弧下标 int pre[maxn]; //可增广路上的上一条弧的编号 struct node { int v, cap; int next; }edge[maxm]; void add(int u, int v, int cap)//加边,储存地图 { edge[bnum].v=v; edge[bnum].cap=cap; edge[bnum].next=head[u]; head[u]=bnum++; edge[bnum].v = u; edge[bnum].cap=0; edge[bnum].next=head[v]; head[v] = bnum++; } void BFS(int source,int sink)//预处理,利用反向BFS,更新dis数组 { queue<int>q; while(q.empty()==false) q.pop(); memset(num,0,sizeof(num)); memset(dis,-1,sizeof(dis)); q.push(sink); dis[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dis[v] == -1) { dis[v] = dis[u] + 1;//找允许弧 num[dis[v]]++; q.push(v); } } } } int ISAP(int source,int sink,int n)//n为残量网络中的节点到汇点的最大距离,通常节点的个数 { memcpy(cur,head,sizeof(cur)); int flow=0, u = pre[source] = source; BFS( source,sink);//更新dis数组 while( dis[source] < n ) { if(u == sink) { int df = MAX, pos; for(int i = source;i != sink;i = edge[cur[i]].v)//追踪增广路路径,最小残量df { if(df > edge[cur[i]].cap) { df = edge[cur[i]].cap; pos = i; } } for(int i = source;i != sink;i = edge[cur[i]].v) //更新流量 { edge[cur[i]].cap -= df; edge[cur[i]^1].cap += df; } flow += df; u = pos; } int st; for(st = cur[u];st != -1;st = edge[st].next)// 从当前弧开始查找允许弧 { if(dis[edge[st].v] + 1 == dis[u] && edge[st].cap)//找到允许弧跳出 { break; } } if(st != -1) { cur[u] = st; pre[edge[st].v] = u; u = edge[st].v; } else { if( (--num[dis[u]])==0 ) break;//GAP优化,出现断层结束 int mind = n; for(int id = head[u];id != -1;id = edge[id].next)//retreat操作:更新 dis 数组 { if(mind > dis[edge[id].v] && edge[id].cap) { cur[u] = id;//修改标号的同时修改当前弧 mind = dis[edge[id].v]; } } dis[u] = mind+1; num[dis[u]]++; if(u!=source) u = pre[u];// 回溯继续寻找允许弧 } } return flow; } void initt() { memset(head,-1,sizeof(head)); bnum=0; } int main() { int T, N,M,a,b,c; int maa, sum, source, sink, n; scanf("%d", &T); for (int cas = 1; cas <= T; ++cas) { initt(); sum = 0; source = 0; maa = 0; scanf("%d%d", &N, &M); for (int i = 1; i <= N; i++) { scanf("%d%d%d", &a, &b, &c); sum += a; if(c > maa) maa = c; add(source, i, a); for (int j = b; j <= c; ++j) { add(i, N + j, 1); } } sink = N + maa + 1; n = sink; for (int i = 1; i <= maa; ++i) { add(N + i, sink, M); } printf("Case %d: ", cas); int ans = ISAP(source, sink, n); if(ans==sum) puts("Yes"); else puts("No"); cout<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。