hdu2883
2024-09-03 17:29:19
题解:
网络流
用一个离散化
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=<<;
int si[],ei[],ni[],ti[],head[],h[],num[];
int a[],n,m,sum;
int cnt,ans,c;
struct edge
{
int x,y,flow,nxt,op;
}em[];
void add(int x,int y,int c)
{
em[++cnt].x=x;
em[cnt].y=y;
em[cnt].flow=c;
em[cnt].nxt=head[x];
head[x]=cnt;
em[cnt].op=cnt+;
cnt++;
em[cnt].x=y;
em[cnt].y=x;
em[cnt].flow=;
em[cnt].nxt=head[y];
head[y]=cnt;
em[cnt].op=cnt-;
}
int dfs(int x,int flow)
{
if(x==n+c)
return flow;
int temp=flow,pos=n+c+;
for (int j=head[x];j;j=em[j].nxt)
{
int y=em[j].y;
int w=em[j].flow;
if (h[x]==h[y]+&&w>)
{
int temp_flow=dfs(y,min(temp,w));
temp-=temp_flow;
em[j].flow-=temp_flow;
em[em[j].op].flow+=temp_flow;
if (!temp||h[]==n+c+)
return flow-temp;
}
if (w>&&h[y]<pos)pos=h[y];
}
if (temp==flow)
{
num[h[x]]--;
if (num[h[x]]==)h[]=n+c+;
else
{
h[x]=pos+;
num[h[x]]++;
}
}
return flow-temp;
}
void isap()
{
memset(h,,sizeof(h));
memset(num,,sizeof(num));
while (h[]<n+c+)ans+=dfs(,INF);
if (ans==sum)puts("Yes");
else puts("No");
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
sum=;
int tot=;
cnt=;
memset(head,,sizeof(head));
for (int i=;i<=n;i++)
{
scanf("%d%d%d%d",si+i,ni+i,ei+i,ti+i);
a[++tot]=si[i];
a[++tot]=ei[i];
add(,i,ni[i]*ti[i]);
sum+=ni[i]*ti[i];
}
sort(a+,a+tot+);
c=;
for (int i=;i<=tot;i++)
if (a[c]!=a[i])a[++c]=a[i];
for (int i=;i<c;i++)
{
int num=(a[i+]-a[i])*m;
add(n+i,n+c,num);
}
for (int i=;i<=c-;i++)
for (int j=;j<=n;j++)
if (si[j]<=a[i]&a[i+]<=ei[j])add(j,i+n,INF);
ans=;
isap();
}
return ;
}
最新文章
- python协程和yeild
- Android自动化测试中Monkeyrunner详解
- .net 根据匿名类生成实体类,根据datatable生成实体类,根据sql生成实体类
- C标准库<;signal.h>;实现
- Nginx安装第二步手动下载依赖包
- magento性能优化的教程(非常详细)
- nginx args
- 未能加载文件或程序集“DAL”或其他的某一个依赖项,系统找不到指定的文件
- zabbix3.2在lamp环境安装
- OpenCV探索之路(十六):图像矫正技术深入探讨
- 利用ICSharpCode.SharpZipLib进行压缩
- 【Python】正则表达式re
- String&;StringBuilder&;StringBuffer总结
- org.springframework.web.servlet.PageNotFound
- Spring Boot Jpa 的使用
- [Git] 拉开发分支的代码报错
- Task.Run Vs Task.Factory.StartNew 【收藏】
- qt tcp 通信实例
- Kafka错误“Network is unreachable”和“larger than available brokers”
- SSH小问题:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
热门文章
- supervisord部署
- Expedition---poj2431(优先队列-堆的实现)
- Agent XPs disable
- 统计编程的框架与R语言统计分析基础——摘(1)
- (转)JavaScriptSerializer,DataContractJsonSerializer解析JSON字符串功能小记
- CCF地铁修建
- Android开发--取消AsyncTask
- docker 删除所有的 docker ps -a 记录
- eclipse中gradle插件安装
- Python笔记 #14# Pandas: Selection