今天学了一点离散化的技巧 果然精妙绝伦啊
题意:
烤肉店有N个人来, 每个人对应时间si到达烤肉店 ,ei时离开烤肉店(ei这个时刻是呆在烤肉店的), 每个人点了ni串烤肉 每一串烤肉烤熟需要花费ti的时间,问是否能满足每个顾客的需求.
这道题第一眼看上去就是跟hdu3572一样的做法 但是不同之处在于 这道题si和ei的范围开的很大 如果把每一个时间点看作一个点来连接图的话肯定会TLE 所以直接搜了一下博客 发现大牛们都用的离散化
首先 把每个顾客的si和ei都记录下来 同时把si和ei存在temp[ ]这个数组里 然后对temp[ ]数组进行排序和去重
例如 第一位顾客 2~9时间段在烤肉店
第二位顾客 3~6时间段在烤肉店
第三位顾客 5~6时间段在烤肉店
我用temp[ ]这个数组来保存这些时间点 经过排序和去重后
temp保存的数据如下: 2 3 5 6 9 一共保存了5个时间点
这里定义了一个变量cnt来记录无重复的时间点的个数 这里cnt=5
这5个时间点就构成了4个区间
4个区间分别为 2~3 3~5 5~6 6~9
下面我们1~n循环来遍历顾客 且令顾客的节点编号为1~n 令每段时间区间为一个点 所以这里时间区间的节点编号为 n+1~n+cnt-1
每一次循环 遍历上述的4个区间
我们来看第一位顾客 第一位顾客的si和ei分别为2和9
第一个区间为2~3 2<=2 且9>=3 说明这个区间的任何时间 顾客都呆在这里 所以这段区间可以给这位顾客做考肉 所以我们就addedge(1,n+1,INF)
同理第一位顾客在第二段第三段第四段区间中都呆在店里 所以分别连边
同理 第二位顾客要向3~5 和5~6对应的节点进行连边, 第三位顾客只向5~6时间段对应的节点连边就可以了
或许读者可以看到 在连接顾客与时间区间的时候 边的权值设置了INF 那么我们如何来限制呢
建立超级源点 编号为0
将汇点与每一位顾客连起来 权值为need[i]*cost[i]
建立超级汇点 编号为 n+cnt+1 将每个时间区间对应的节点与汇点连接起来 权值为(temp[i]-temp[i-1])*m
只需求出最大流看是否等于∑need[i]*cost[i]就可以了
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<map>
#include<set>
typedef long long ll;
using namespace std;
const int MAXN=20010;//点数的最大值
const int MAXM=880010;//边数的最大值
const int INF=0x3f3f3f3f;
struct Node
{
int from,to,next;
int cap;
}edge[MAXM];
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y
int n;//n是总的点的个数，包括源点和汇点
void init() //在main函数的开头写init别忘了!
{
tol=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w)
{
edge[tol].from=u;
edge[tol].to=v;
edge[tol].cap=w;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].from=v;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].next=head[v];
head[v]=tol++;
}
void BFS(int start,int end)
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=1;
int que[MAXN];
int front,rear;
front=rear=0;
dep[end]=0;
que[rear++]=end;
while(front!=rear)
{
int u=que[front++];
if(front==MAXN)front=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]!=-1)continue;
que[rear++]=v;
if(rear==MAXN)rear=0;
dep[v]=dep[u]+1;
++gap[dep[v]];
}
}
}
int SAP(int start,int end)
{
int res=0;
BFS(start,end);
int cur[MAXN];
int S[MAXN];
int top=0;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep[start]<n)
{
if(u==end)
{
int temp=INF;
int inser;
for(i=0;i<top;i++)
if(temp>edge[S[i]].cap)
{
temp=edge[S[i]].cap;
inser=i;
}
for(i=0;i<top;i++)
{
edge[S[i]].cap-=temp;
edge[S[i]^1].cap+=temp;
}
res+=temp;
top=inser;
u=edge[S[top]].from;
}
if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路
break;
for(i=cur[u];i!=-1;i=edge[i].next)
if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
break;
if(i!=-1)
{
cur[u]=i;
S[top++]=i;
u=edge[i].to;
}
else
{
int min=n;
for(i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].cap==0)continue;
if(min>dep[edge[i].to])
{
min=dep[edge[i].to];
cur[u]=i;
}
}
--gap[dep[u]];
dep[u]=min+1;
++gap[dep[u]];
if(u!=start)u=edge[S[--top]].from;
}
}
return res;
}
int s[205];
int e[205];
int need[205];
int cost[205];
int temp[405];
int main()
{
int i,j,k,m,n1;
while(scanf("%d%d",&n1,&m)==2)
{
init();
j=0;
int sum=0;
for(i=1;i<=n1;i++)
{
scanf("%d%d%d%d",&s[i],&need[i],&e[i],&cost[i]);
temp[++j]=s[i];
temp[++j]=e[i];
sum+=need[i]*cost[i];
}
sort(temp+1,temp+1+j);
int cnt=unique(temp+1,temp+1+j)-temp-1;
int source=0;
int sink=n1+cnt+1;
for(i=1;i<=n1;i++)
{
addedge(source,i,need[i]*cost[i]);
for(j=2;j<=cnt;j++)
{
if(s[i]<=temp[j-1]&&e[i]>=temp[j])
{
addedge(i,n1+j-1,INF);
}
}
}
for(i=2;i<=cnt;i++)
{
addedge(i-1+n1,sink,(temp[i]-temp[i-1])*m);
}
n=n1+cnt+2;
int tt=SAP(source,sink);
if(tt==sum)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}