luogu P2570 [ZJOI2010]贪吃的老鼠【二分+最大流】

首先考虑只满足第一个条件，二分答案，把过期时间加上mid之后的2n个时间离散，老鼠拆成每个时间的，第i个时间第j个老鼠为id[i][j]，连接(s,i,p[i])，对于离散后时间(g[j-1]~g[j])在i奶酪的时间区间里的ij，连接(i,id,老鼠速度*时间段长)，然后连(id,t,inf)，判断合法就是dinic==sump

易证这样是满足第一个条件的，因为可以调整吃奶酪的老鼠的顺序来使其合法

然后看第二个条件，把老鼠速度从大到小排序并差分，把上个建图中的(i,id,老鼠速度*时间段长)改成(i,id,老鼠差分速度*时间段长)，(id,t,inf)改成(id,t,老鼠排名*老鼠差分速度*时间段长)

这样的原理是把大的速度分成若干小段，然后把问题变成选这些小段，而小段的数量是被限制的，所以这些小段拼起来一定是若干不同的老鼠

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int N=20005;

const double eps=1e-6;

int T,n,m,p[N],l[N],r[N],a[N],h[N],cnt=1,le[N],s,t,sm,id[105][105],con;

double g[N];

struct qwe

{

	int ne,to;

	double va;

}e[N*20];

int read()

{

	int l=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		l=l*10+p-48;

		p=getchar();

	}

	return l*f;

}

bool cmp(const int &a,const int &b)

{

	return a>b;

}

void add(int u,int v,double w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void ins(int u,int v,double w)

{

	add(u,v,w);

	add(v,u,0);

}

bool bfs()

{

	queue<int>q;

	memset(le,0,sizeof(le));

	le[s]=1;

	q.push(s);

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		for(int i=h[u];i;i=e[i].ne)

			if(e[i].va>0&&!le[e[i].to])

			{

				le[e[i].to]=le[u]+1;

				q.push(e[i].to);

			}

	}

	return le[t];

}

double dfs(int u,double f)

{

	if(u==t||!f)

		return f;

	double us=0;

	for(int i=h[u];i&&us<f;i=e[i].ne)

		if(e[i].va>0&&le[e[i].to]==le[u]+1)

		{

			double t=dfs(e[i].to,min(e[i].va,f-us));

			e[i].va-=t;

			e[i^1].va+=t;

			us+=t;

		}

	if(us<eps)

		le[u]=0;

	return us;

}

double dinic()

{

	double r=0;

	while(bfs())

		r+=dfs(s,1e18);

	return r;

}

bool ok(double w)

{

	memset(h,0,sizeof(h));

	cnt=1;

	for(int i=1;i<=n;i++)

		ins(s,i,p[i]),g[i]=l[i],g[i+n]=r[i]+w;

	sort(g+1,g+1+2*n);

	for(int i=2;i<=2*n;i++)

		if(g[i]-g[i-1]>eps)

			for(int j=1;j<=m;j++)

			{

				ins(id[i][j],t,(g[i]-g[i-1])*j*a[j]);

				for(int k=1;k<=n;k++)

					if(g[i-1]>=l[k]&&g[i]<=r[k]+w)

						ins(k,id[i][j],(g[i]-g[i-1])*a[j]);

			}

	// double nw=dinic();cerr<<nw<<" "<<sm<<endl;

	return dinic()-sm>=0;

}

int main()

{

	T=read();

	while(T--)

	{

		con=n=read(),m=read(),sm=0;

		for(int i=1;i<=n;i++)

			p[i]=read(),l[i]=read(),r[i]=read(),sm+=p[i];

		for(int i=1;i<=m;i++)

			a[i]=read();

		sort(a+1,a+1+m,cmp);

		for(int i=1;i<m;i++)

			a[i]-=a[i+1];

		for(int i=1;i<=2*n;i++)

			for(int j=1;j<=m;j++)

				id[i][j]=++con;

		s=0,t=con+1;

		double l=0,r=1e7,ans=r;

		while(r-l>eps)

		{

			double mid=(l+r)/2;

			if(ok(mid))

				r=mid,ans=mid;

			else

				l=mid;

		}

		printf("%.4f\n",ans);

	}

	return 0;

}

巴特西

luogu P2570 [ZJOI2010]贪吃的老鼠【二分+最大流】

最新文章

热门文章