题目
题解
感觉就是道多合一……
先处理出来$n$到$1…n1$的最短距离，即求$\frac{\sum_{j\in path(n,i)}t_j}{\sum_{j\in path(n,i)}s_j}$最大，一脸分数规划的样子，设二分的答案为$T$，则有$\sum_{j\in path(n,i)}t_j -T\times \sum_{j\in path(n,i)}s_j\le 0$
即$\sum_{j\in path(n,i)}t_j -T\times s_j\le 0$，把每条边赋值成$t-T\times s$，求$n$到$i$的最短路即可，因为这个图是个$DAG$，直接拓扑排序处理
处理完之后要求和的最小值，一脸最小割的样子，$u$连$v\inf$边，然后$S$连奇数点，偶数点连$T$，跑个网络流即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,inf=1e8;
const double fs=1e-6;
struct p{
int x,y;
double d;
}c[MAX];
int n,m,n1,m1,num=1,T;
int d[MAX],H[MAX],qu[MAX],h[MAX];
double Ans;
double ans[MAX];
bool use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
struct Top{
struct p{
int x,y,s,t;
}c[MAX];
int num;
int h[MAX],Du[MAX],du[MAX],qu[MAX];
double f[MAX];
void add(int x,int y,int s,int t) {++Du[y],c[++num]=(p){h[x],y,s,t},h[x]=num;}
bool look(double mid,int x)
{
int hl=1,tl=0;
for(int i=1;i<=n;++i)
du[i]=Du[i],f[i]=inf,!du[i]?qu[++tl]=i:0;
f[n]=0;
while(hl<=tl)
{
int tt=qu[hl++];
if(tt==x) return f[x]<=fs;
for(int i=h[tt],y;i;i=c[i].x)
{
y=c[i].y,f[y]=min(f[y],f[tt]+c[i].t-mid*c[i].s);
if(!--du[y]) qu[++tl]=y;
}
}
return f[x]<=fs;
}
double Solve(int x)
{
double l=0,r=10*m,ans=inf;
while(l<=r)
{
double mid=(l+r)/2;
if(look(mid,x)) ans=mid,r=mid-fs;
else l=mid+fs;
}
return ans;
}
void Solve()
{
for(int i=1,a,b,s,t;i<=m;++i)
a=read(),b=read(),t=read(),s=read(),add(a,b,s,t);
m1=read(),n1=read();
for(int i=1;i<=n1;++i)
ans[i]=Solve(i);
}
}A;
void add(int x,int y,double d)
{
c[++num]=(p){h[x],y,d},h[x]=num;
c[++num]=(p){h[y],x,0},h[y]=num;
}
bool bfs()
{
memset(d,0,sizeof(d));
int hl=1,tl=d[0]=1;
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=h[tt],y;i;i=c[i].x)
if(c[i].d>fs&&!d[y=c[i].y])
{
d[y]=d[tt]+1,qu[++tl]=y;
if(y==T) return 1;
}
}
return 0;
}
double dfs(int x=0,double dix=inf)
{
if(x==T||dix<=fs) return dix;
double sum=0;
for(int &i=H[x],y;i;i=c[i].x)
if(c[i].d>fs&&d[y=c[i].y])
{
double dis=dfs(y,min(dix,c[i].d));
if(dis>fs)
{
sum+=dis,dix-=dis,c[i].d-=dis,c[i^1].d+=dis;
if(dix<=fs) break;
}
}
if(sum<=fs) d[x]=-2;
return sum;
}
double Dinic()
{
double tot=0,D;
while(bfs())
{
memcpy(H,h,sizeof(h));
while(D=dfs()) tot+=D;
}
return tot;
}
int main()
{
n=read(),m=read(),A.Solve(),T=n1+1;
for(int i=1;i<=n1;++i)
i&1?add(0,i,ans[i]):add(i,T,ans[i]);
for(int i=1,u,v;i<=m1;++i)
u=read(),v=read(),add(u,v,inf);
Ans=Dinic();
if(Ans>inf) return printf("-1"),0;
return printf("%.1lf",Ans),0;
}
