YbtOJ 581「网络流」图上旅行

//题出的很好，下次别出了。
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=550,M=2010,K=2010;long double inf=1e12;
int n,m,k,d[N],fir[N],nxt[M],son[M],tot,fr[M],r[M],S,T,cnt,p[M];
I void Add(CI x,CI y){nxt[++tot]=fir[x],fr[tot]=x,fir[x]=tot,son[tot]=y,d[x]++;}
#define to son[i]
vector<int> G[N];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<PA> v[N]; 
#define pb push_back
queue<int> q;
#define eps 1e-7
long double f[N];
namespace Flow{
    int fir[M],nxt[M<<2],son[M<<2],tot,cur[M],dis[M];long double w[M<<2];
    I void Add(CI x,CI y,long double z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0;}
    #define to son[i]
    queue<int> q;
    I bool bfs(){W(!q.empty()) q.pop();q.push(S);memset(dis,-1,sizeof(dis));dis[S]=0;W(!q.empty()){RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>eps&&dis[to]==-1) dis[to]=dis[u]+1,q.push(to);}return ~dis[T];}
    I long double dfs(CI x,long double flow){if(x==T) return flow;RI i;long double d,now=flow;for(i=cur[x];i;i=nxt[i]) if(cur[x]=nxt[i],w[i]>eps&&dis[to]==dis[x]+1){d=dfs(to,min(w[i],now));d>eps&&(w[i]-=d,w[i^1]+=d,now-=d,0);if(now<=eps) break ;}return flow-now;}
    I long double F(){RI i;long double Ans=0;W(bfs()){for(i=1;i<=cnt;i++) cur[i]=fir[i];Ans+=dfs(S,inf);}return Ans;}
    I void C(){memset(fir,0,sizeof(fir)),tot=1;}
}
I bool chk(CI x,long double mid){
    RI i,t;long double X=0;for(Flow::C(),i=1;i<=cnt-2;i++) r[p[i]]=i,f[t=son[p[i]]]-mid>0?X+=f[t]-mid,Flow::Add(S,i,f[t]-mid):Flow::Add(i,T,mid-f[t]);
    for(auto i:v[x]) Flow::Add(r[i.fi],r[i.se],inf);
    return X-Flow::F()>eps;
}
int main(){
    freopen("trip.in","r",stdin),freopen("trip.out","w",stdout);
    long double l,r,mid;RI i,x,y,u;for(read(n,m,k),i=1;i<=m;i++) read(x,y),Add(x,y),G[y].pb(x);for(i=1;i<=k;i++) read(x,y),v[fr[x]].pb(MP(x,y));for(i=1;i<=n;i++) !d[i]&&(q.push(i),0);W(!q.empty()){
        u=q.front(),q.pop();for(auto i:G[u]) !--d[i]&&(q.push(i),0);for(cnt=0,i=fir[u];i;i=nxt[i]) p[++cnt]=i;if(!cnt) continue ;S=++cnt,T=++cnt,l=0,r=n;
        W(r-l>eps) mid=(l+r)/2.0,chk(u,mid)?l=mid:r=mid;f[u]=l+1;
    }return printf("%.14Lf\n",f[1]),0;
}