已经修改时限为2s
请重试
by icy @ 2017-08-19 19:28:15
@[icy](/space/show?uid=20487) 谢谢了
by Idvz @ 2017-08-22 21:50:21
```
#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
typedef double db;
const db eps=1e-3;
const int N=705,M=100005,inf=0x3f3f3f3f;
int n,m,n1,m1;
db dis[N],ans;
namespace graph{
int tot,top,js;
int h[N],ne[M],to[M],tt[M],ss[M],du[N],st[N],p[N];
int q[N],k1[N],k2[N];db f[N];
void add(int x,int y,int s,int t)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,ss[tot]=s,tt[tot]=t,++du[y];}
void topsort() {
for(RI i=1;i<=n;++i) if(!du[i]) st[++top]=i;
while(top) {
int x=st[top];--top,p[++js]=x;
for(RI i=h[x];i;i=ne[i]) {
--du[to[i]];
if(!du[to[i]]) st[++top]=to[i];
}
}
}
void shortest_way(db kans) {
for(RI i=1;i<=n;++i) f[i]=inf; f[n]=0;
for(RI i=1;i<=n;++i) {
int x=p[i];
for(RI j=h[x];j;j=ne[j])
f[to[j]]=min(f[to[j]],f[x]+(db)tt[j]-(db)ss[j]*kans);
}
}
void slove(db l,db r,int ql,int qr) {
if(ql>qr) return;
if(fabs(r-l)<eps) {for(RI i=ql;i<=qr;++i) dis[q[i]]=(l+r)/2.0;return;}
db mid=(l+r)/2.0;int js1=0,js2=0;
shortest_way(mid);
for(RI i=ql;i<=qr;++i)
if(f[q[i]]<0) k1[++js1]=q[i];
else k2[++js2]=q[i];
for(RI i=1;i<=js1;++i) q[ql+i-1]=k1[i];
for(RI i=1;i<=js2;++i) q[ql+js1+i-1]=k2[i];
slove(l,mid,ql,ql+js1-1),slove(mid,r,ql+js1,qr);
}
void work() {
topsort();
for(RI i=1;i<=n1;++i) q[i]=i;
slove(0,11,1,n1);
for(RI i=1;i<=n1;++i) if(dis[i]-eps>10.0) dis[i]=inf;
}
}
namespace maxflow{
int S,T,tot=1;
int h[N],ne[M<<1],to[M<<1],lev[N],que[N];db flow[M<<1];
void add(int x,int y,db z) {
to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z;
to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0;
}
int bfs() {
for(RI i=1;i<=T;++i) lev[i]=0;
int he=1,ta=1;lev[S]=1,que[1]=S;
while(he<=ta) {
int x=que[he];++he;
if(x==T) return 1;
for(RI i=h[x];i;i=ne[i])
if(fabs(flow[i])>eps&&!lev[to[i]])
lev[to[i]]=lev[x]+1,que[++ta]=to[i];
}
return 0;
}
db dfs(int x,db liu) {
if(x==T) return liu;
db sum=0;
for(RI i=h[x];i;i=ne[i])
if(fabs(flow[i])>eps&&lev[to[i]]==lev[x]+1) {
db kl=dfs(to[i],min(flow[i],liu-sum));
flow[i]-=kl,flow[i^1]+=kl,sum+=kl;
if(fabs(liu-sum)<eps) return sum;
}
if(fabs(sum)<eps) lev[x]=-1;
return sum;
}
void work() {
S=n1+1,T=n1+2;int x,y;
for(RI i=1;i<=n1;i+=2) add(S,i,dis[i]);
for(RI i=2;i<=n1;i+=2) add(i,T,dis[i]);
for(RI i=1;i<=m1;++i) {
x=read(),y=read();
if(!(x&1)) swap(x,y);
add(x,y,inf);
}
while(bfs()) ans+=dfs(S,inf);
}
}
int main()
{
n=read(),m=read();
for(RI i=1;i<=m;++i) {
int x=read(),y=read(),t=read(),s=read();
graph::add(x,y,s,t);
}
m1=read(),n1=read();
graph::work();maxflow::work();
if(ans>1e9) puts("-1");
else printf("%.1lf\n",ans);
return 0;
}
```
by _Francis_ @ 2023-02-19 13:18:49