【BZOJ2285】[SDOI2011]保密（分数规划，网络流）

题面

BZOJ

洛谷

题解

首先先读懂题目到底在干什么。

发现要求的是一个比值的最小值，二分这个最小值\(k\)，把边权转换成\(t-sk\)，其中\(t\)是时间，\(s\)是安全系数。那么通过一遍\(SPFA\)可以求出到达所有的目标点的危险性的最小值，用\(SPFA\)是因为存在负边权。显然到达每个位置的危险性最小值是独立计算的。

因为是每个空腔都要探索其出入口中的一个，不难发现这个东西就是一个最小割（似乎是最大权闭合子图？？？）。那么再跑一遍网络流就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

#define MAX 1010

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

const double eps=1e-3;

namespace MaxFlow

{

	struct Line{int v,next;double w;}e[200000];

	int h[MAX],cnt=2;

	inline void Add(int u,int v,double w)

	{

		e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

		e[cnt]=(Line){u,h[v],0};h[v]=cnt++;

	}

	int level[MAX];

	int S,T,cur[MAX];

	bool bfs()

	{

		memset(level,0,sizeof(level));level[S]=1;

		queue<int> Q;Q.push(S);

		while(!Q.empty())

		{

			int u=Q.front();Q.pop();

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

				if(fabs(e[i].w)>eps&&!level[e[i].v])

					Q.push(e[i].v),level[e[i].v]=level[u]+1;

		}

		return level[T];

	}

	double dfs(int u,double flow)

	{

		if(u==T||fabs(flow)<eps)return flow;

		double ret=0;

		for(int &i=cur[u];i;i=e[i].next)

		{

			int v=e[i].v;double d;

			if(fabs(e[i].w)>eps&&level[v]==level[u]+1)

			{

				d=dfs(v,min(flow,e[i].w));

				ret+=d,flow-=d;

				e[i].w-=d;e[i^1].w+=d;

			}

		}

		return ret;

	}

	double Dinic()

	{

		double ret=0;

		while(bfs())

		{

			memcpy(cur,h,sizeof(h));

			ret+=dfs(S,1e18);

		}

		return ret;

	}

}

int n,m,n1,m1;

double Sv[MAX];

namespace Graph

{

	struct Line{int v,next,t,s;}e[200200];

	int h[MAX],cnt=1;

	inline void Add(int u,int v,int t,int s){e[cnt]=(Line){v,h[u],t,s};h[u]=cnt++;}

	double dis[MAX];bool vis[MAX];

	double SPFA(int T,double mid)

	{

		for(int i=1;i<=n;++i)dis[i]=1e18,vis[i]=false;

		dis[n]=0;queue<int>Q;Q.push(n);vis[n]=true;

		while(!Q.empty())

		{

			int u=Q.front();Q.pop();

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

			{

				int v=e[i].v;double w=e[i].t-mid*e[i].s;

				if(dis[v]>dis[u]+w)

				{

					dis[v]=dis[u]+w;

					if(!vis[v])vis[v]=true,Q.push(v);

					if(v==T&&dis[v]<eps)return dis[T];

				}

			}

			vis[u]=false;

		}

		return dis[T];

	}

	void work()

	{

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

		{

			double l=0,r=11,ret=1e9;

			while(r-l>1e-3)

			{

				double mid=(l+r)/2;

				if(SPFA(i,mid)<eps)r=mid,ret=mid;

				else l=mid;

			}

			Sv[i]=ret;

		}

	}

}

int main()

{

	n=read();m=read();

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

	{

		int u=read(),v=read(),s=read(),t=read();

		Graph::Add(u,v,s,t);

	}

	m1=read();n1=read();

	Graph::work();

	MaxFlow::S=0;MaxFlow::T=n1+1;

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

		if(i&1)MaxFlow::Add(MaxFlow::S,i,Sv[i]);

		else MaxFlow::Add(i,MaxFlow::T,Sv[i]);

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

	{

		int u=read(),v=read();

		MaxFlow::Add(u,v,1e9);

	}

	double ans=MaxFlow::Dinic();

	if(ans>1e9)puts("-1");

	else printf("%.1lf\n",ans);

	return 0;

}