hdu3572Task Schedule 最大流,判断满流 优化的SAP算法
2024-08-24 16:34:26
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=,M=, 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=;
for(i=;i<=n;i++)
cure[i]=head[i];
numh[]=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^].w+=flow;
}
ans+=flow;
u=neck;
}
for(i=cure[u];i!=-;i=edge[i].next)
if(edge[i].w && h[u]==h[edge[i].to]+) break;
if(i!=-) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}
else
{
if(==--numh[h[u]]) break; //GAP优化
cure[u]=head[u];
for(tmp=n,i=head[u];i!=-;i=edge[i].next)
if(edge[i].w) tmp=min(tmp, h[edge[i].to]);
h[u]=tmp+;
++numh[h[u]];
if(u!=s) u=pre[u];
}
}
}
void init()
{
tot=;
memset(head,-,sizeof(head));
memset(pre,-,sizeof(pre));
memset(h,,sizeof(h));
memset(numh,,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=;edge[tot].next=head[j];head[j]=tot++;
}
int main()
{
//freopen("test.txt","r",stdin);
int n,m,i,j,k,cas,t=,a,b,c,MAX,sum,s;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
init();
MAX=;sum=;s=n+;
for(i=;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,);
}
k=s++MAX;
for(i=;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 ;
}
最新文章
- check_env函数解析
- js一些代码方法
- Spark Scala 读取GBK文件的方法
- 使用jQuery开发一个响应式超酷整合RSS信息阅读杂志
- iOS学习笔记---c语言第二天
- Word2010 清除样式
- struct2-json
- Binder的非正常消亡时的重置方法
- 轻量级别的Cache和反向代理软件---Varnish
- Python数据分析之路(一)查询和统计
- 阿里云服务器实战(一) : 在Linux下Tomcat7下使用连接池
- 2019春第七周作业Compile Summarize
- 技术笔记1:java.sql.SQLException: Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password)
- 【Loadrunner】Loadrunner 手动关联技术
- JS 对象(对象遍历,拷贝)
- 用MVC5+EF6+WebApi 做一个小功能(四) 项目分层功能以及文件夹命名
- WCF 基于 WinForm 宿主 发布
- [转]jmeter实战
- Python之风湿理论值函数即变量
- Microsoft SQL Server2008安装教程