首先通过分数规划,二分答案$mid$,将每条边边权重置为$t-mid\times s$,用DP求出终点到该点的最短路,若非正则可以更小。
如此可以计算出每个出入口的最小危险值,然后把奇点放在$S$,偶点放在$T$,代价为危险值,对于每个空腔,在相应点之间连无穷边,求最小割即可。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=705,M=100010;
const double inf=1e9,eps=3e-4;
int n,m,n1,m1,i,x,y,d[N],g[N],v[M],wt[M],ws[M],nxt[M],ed,h,t,q[N],vis[N];double f[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void add(int x,int y){d[y]++;v[++ed]=y;read(wt[ed]);read(ws[ed]);nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
if(vis[x])return;
vis[x]=1;
for(int i=g[x];i;i=nxt[i])dfs(v[i]);
}
inline bool check(int T,double p){
int i,x,j;
for(i=1;i<n;i++)f[i]=inf;
for(i=1;i<=n;i++){
x=q[i];
if(x==T)return f[x]<eps;
for(j=g[x];j;j=nxt[j])f[v[j]]=min(f[v[j]],f[x]+wt[j]-p*ws[j]);
}
}
inline double cal(int x){
if(!vis[x])return inf;
double l=0.1,r=10,mid;
while(l+eps<r)if(check(x,mid=(l+r)/2))r=mid;else l=mid;
return(l+r)/2;
}
namespace Flow{
struct E{int t;double f;E*nxt,*pair;}*g[N],*d[N],pool[90000],*cur=pool;
int S,T,h[N],gap[N];double ans;
inline void add(int s,int t,double f){
E*p=cur++;p->t=t;p->f=f;p->nxt=g[s];g[s]=p;
p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p;
g[s]->pair=g[t];g[t]->pair=g[s];
}
double sap(int v,double flow){
if(v==T)return flow;
double rec=0;
for(E*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f>eps){
double ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret;p->pair->f+=ret;d[v]=p;
rec+=ret;
if(rec+eps>flow)return flow;
}
if(!(--gap[h[v]]))h[S]=T;
gap[++h[v]]++;d[v]=g[v];
return rec;
}
void solve(){
for(gap[0]=T,i=1;i<=T;i++)d[i]=g[i];
while(h[S]<T)ans+=sap(S,inf);
if(ans>1e8)puts("-1");else printf("%.1f",ans);
}
}
int main(){
read(n),read(m);
for(i=1;i<=m;i++)read(x),read(y),add(x,y);
dfs(n);
for(h=i=1;i<=n;i++)if(!d[i])q[++t]=i;
while(h<=t)for(i=g[x=q[h++]];i;i=nxt[i])if(!(--d[v[i]]))q[++t]=v[i];
read(m1),read(n1);
Flow::S=n1+1;
Flow::T=n1+2;
for(i=1;i<=n1;i++)if(i&1)Flow::add(n1+1,i,cal(i));else Flow::add(i,n1+2,cal(i));
while(m1--)read(x),read(y),Flow::add(x,y,inf);
Flow::solve();
return 0;
}