首页 > 代码库 > hdu3572Task Schedule 最大流，判断满流 优化的SAP算法
hdu3572Task Schedule 最大流，判断满流 优化的SAP算法
PS:多校联赛的题目质量还是挺高的。建图不会啊，看了题解才会的。
参考博客：http://blog.csdn.net/luyuncheng/article/details/7944417
看了上面博客里的题解，思路就有了。不过建图还是有点麻烦。我把源点设为n+1 (不想从0开始，不修改模版)，汇点就是n+2+MAX,其中MAX是题目中Ei的最大值。
这题，我有疑问：优化过的SAP算法的时间复杂度是O(m*n^2),此题的n最大为1000，m为50万，时间超过5亿了。1s的时限居然过了。
其中有个小插曲，我想了好久才明白的。为什么是判断满流，最后一定要用 “==”？ >=不可以么？最后想明白了，其实求出来的最大流的值一定是<= sum的。因为从源点出来的流值最大也才sum。
下面是代码： 建图会了用模版就可以了。模版参考哈工大的《图论及应用》。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1010,M=510000, INF=0x3f3f3f3f;struct node{ int to,next,w;}edge[M];int head[N],numh[N],h[N],cure[N],pre[N];//numh:GAP优化的统计高度数量数组; h：距离标号数组; cure:当前弧int ans,tot;void SAP(int s, int e,int n){ int flow,u,tmp,neck,i; ans=0; for(i=1;i<=n;i++) cure[i]=head[i]; numh[0]=n; u=s; while(h[s]<n) { if(u==e) { flow =INF; for(i=s;i!=e;i=edge[cure[i]].to) { if(flow>edge[cure[i]].w) { neck=i; flow =edge[cure[i]].w; } } for(i=s;i!=e;i=edge[cure[i]].to) { tmp=cure[i]; edge[tmp].w-=flow; edge[tmp^1].w+=flow; } ans+=flow; u=neck; } for(i=cure[u];i!=-1;i=edge[i].next) if(edge[i].w && h[u]==h[edge[i].to]+1) break; if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} else { if(0==--numh[h[u]]) break; //GAP优化 cure[u]=head[u]; for(tmp=n,i=head[u];i!=-1;i=edge[i].next) if(edge[i].w) tmp=min(tmp, h[edge[i].to]); h[u]=tmp+1; ++numh[h[u]]; if(u!=s) u=pre[u]; } }}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(pre,-1,sizeof(pre)); memset(h,0,sizeof(h)); memset(numh,0,sizeof(numh));}void addedge(int i,int j,int w){ edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k,cas,t=1,a,b,c,MAX,sum,s; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); init(); MAX=0;sum=0;s=n+1; for(i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); sum+=a; MAX=max(MAX,c); addedge(s,i,a); for(j=b;j<=c;j++) addedge(i,j+s,1); } k=s+1+MAX; for(i=1;i<=MAX;i++) addedge(s+i,k,m); SAP(s,k,k); printf("Case %d: ",t++); if(ans==sum) printf("Yes\n\n"); else printf("No\n\n"); } return 0;}
hdu3572Task Schedule 最大流，判断满流 优化的SAP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。