题解 P2494 【[SDOI2011]保密】
w4p3r
·
·
题解
前言
我觉得这是一道好题，因为它考到了许多知识，将很多知识综合了起来
思路
拿到这道题之后，我们应该将这个问题拆成两个问题
第一，求n到每个出入口的时间和与安全系数和比值最小的路径
第二，求出探索所有空腔的最小代价
做法
第一个问题
假设我们去的是点x,那么我们就是要找到一条从n到x的路径，使得\sum (Ti *xi)/\sum (Si*xi )最小，
(xi表示第i条边在不在该路径上，若在为1，不在即为0)
我们考虑二分答案，假设我们当前二分的值为ans,
那如果这个答案满足条件，就要满足 \sum (Ti *xi)/\sum (Si *xi)<=ans，
移项可得\sum (Ti*xi) -\sum (Si*xi)*ans<=0，
即为\sum((Ti-ans*Si)*xi)<=0
那我们只要使每条边权改为Ti-Si*xi,然后看n到x的路径是否<=0即可
这就是一个简单的01分数规划，我相信看这道题的人应该都看得懂qwq
但是要求多个点到n的最小路径，所以考虑整体二分
但貌似听说不整体二分也过得去，如果你不会的话就一个一个二分吧233
最短路用什么方法呢？Spfa?Dijkstra?Floyed?
no no no!!!
首先，这道题有负边，所以Dijkstra首先淘汰，SPFA?,但是这道题m又有足足1e5,跑SPFA巨慢啊，Floyed对于n<=700来说根本不可能
那咋办啊？？
等等，我们是不是漏了什么？
没有环啊！！！
那就简单了，跑个拓扑序就完事了啊（我也不知道我前面扯那么多干嘛）
第二个问题
现在我们得到了n到所有出入口的最小路径，那如何求探索所有空腔的最小代价呢？
首先，我觉得题目都已经在疯狂暗示告诉我们这是个一个二分图了
-----每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为1,3,5…和2,4,6…并且最大的编号为n1。
两排，每个出口一排一个，这不是二分图是什么？？
其实这个网络流模型也并不难建立，
从源点往每个奇数点建边，流量为从n到该点的最小路径
对于每个空腔的两个出入口u,v,假设u是奇数,则从u向v建一条流量为inf的边
从每个偶数点往汇点建边，流量为从n到改点的最小路径
问题是为什么那么建图呢？
其实我们在这里利用的是最小割，因为对于每一个空腔的出入口u,v，我们必须选择一个，让u往v建inf边的意义就是我们为了让u和v分开，我们就必须在u和
然后由最大流最小割定理，跑最小割即可
## 代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define inf 0x7fffffff/2
#define eps 1e-3
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch=getchar();
ll s=0,w=1;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
struct Edge
{
int next,to;
double s,t;
}E[N<<1];
int Head[N],ecnt;
int n,U[N],V[N],m,n1,m1;
int pre[N],minn[N];
double dist[N],D[N];
int depth[N],Index[N];
struct edge
{
int next,to;
double fl;
}e[N*10];
int head[N],cnt=1;
int q[N],ql[N],qr[N];
queue<int>qu;
int vis[N];
int pos[N],nowpos;
int ss,tt,maxflow;
int Stack[N],top;
inline void Add_edge(int from,int to,double s,double t)
{
E[++ecnt].to=to;E[ecnt].next=Head[from];E[ecnt].s=s;E[ecnt].t=t;Head[from]=ecnt;Index[to]++;
}//对原图进行建边
inline void Topu(double x)
{
for(register int i=1;i<n;i++)dist[i]=inf;dist[n]=0;
for(register int i=1;i<=n;i++)
{
int now=pos[i];
for(register int j=Head[now];j;j=E[j].next)
{
dist[E[j].to]=min(dist[E[j].to],dist[now]+E[j].t-E[j].s*x);
}
}
}//求最短路
void Q(double L,double R,int l,int r)
{
if(l>r)return ;
if(fabs(R-L)<=eps){for(register int i=l;i<=r;i++)D[q[i]]=L;return ;}
double mid=(L+R)/2;
Topu(mid);
int nowl=0,nowr=0;
for(register int i=l;i<=r;i++)if(dist[q[i]]<=0.0){ql[++nowl]=q[i];}else qr[++nowr]=q[i];
for(register int i=l;i<=l+nowl-1;i++)q[i]=ql[i-l+1];
for(register int i=l+nowl;i<=r;i++)q[i]=qr[i-nowl-l+1];
Q(L,mid,l,l+nowl-1);Q(mid+eps,R,l+nowl,r);
}//整体二分
inline void add_edge(int from,int to,double fl){e[++cnt].to=to;e[cnt].next=head[from];e[cnt].fl=fl;head[from]=cnt;}
//对网络流建边
inline int bfs()
{
memset(depth,0,sizeof(depth));while(!qu.empty())qu.pop();
qu.push(ss);depth[ss]=1;
while(!qu.empty())
{
int x=qu.front();qu.pop();
for(register int i=head[x];i;i=e[i].next)
{
if(fabs(e[i].fl-0)>=eps&&!depth[e[i].to])depth[e[i].to]=depth[x]+1,qu.push(e[i].to);
}
}
return depth[tt];
}
double dfs(int now,double flow)
{
if(now==tt)return flow;
double ret=0;
for(register int i=head[now];i;i=e[i].next)
{
if(fabs(ret-flow)<=eps)return flow;
if(fabs(e[i].fl-0)>=eps&&depth[e[i].to]==depth[now]+1)
{
double fl=dfs(e[i].to,min(e[i].fl,flow-ret));
if(fabs(fl-0)>=eps)
{
ret+=fl;
e[i].fl-=fl;
e[i^1].fl+=fl;
}
}
}
if(fabs(ret-0)<=eps)depth[now]=0;
return ret;
}
inline double Dinic()
{
double sum=0,x=0;
while(bfs()){x=1;while(fabs(x-0)>=eps){x=dfs(ss,inf);sum+=x;}}
return sum;
}//最大流，即为最小割
inline void Prepare()
{
nowpos=0;top=0;
for(register int i=1;i<=n;i++)if(!Index[i])Stack[++top]=i;
while(top)
{
int x=Stack[top--];pos[++nowpos]=x;
for(register int i=Head[x];i;i=E[i].next)
{
Index[E[i].to]--;if(!Index[E[i].to])Stack[++top]=E[i].to;
}
}
}//求拓扑排序
int main()
{
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++)q[i]=i;
for(register int i=1;i<=m;i++)
{
int from,to;double s,t;
scanf("%d%d%lf%lf",&from,&to,&t,&s);
Add_edge(from,to,s,t);
}
Prepare();
Q(0,inf,1,n-1);D[n]=0;
m1=read(),n1=read();
for(register int i=1;i<=m1;i++)U[i]=read(),V[i]=read();
tt=n1+m1+1;
for(register int i=1;i<=n1;i++)
{
if(i&1)add_edge(ss,i,D[i]),add_edge(i,ss,0);
else add_edge(i,tt,D[i]),add_edge(tt,i,0);
}
for(register int i=1;i<=m1;i++)
{
if(V[i]&1)swap(U[i],V[i]);
add_edge(U[i],V[i],inf),add_edge(V[i],U[i],0);
}
double ans=Dinic();
if(ans>1e8){printf("-1\n");}
else printf("%.1lf\n",ans);
return 0;
}
```
**如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!**