YbtOJ 581「网络流」图上旅
题目链接：YbtOJ #581
小 C 来到了 F 国，小 C 想好好地参观 F 国。F 国可以看一个有 n 个点 m 条边的有向无环图，小 C 刚开始站在 1 号点。
假设现在小 C 站在 x 号点：
- 点 x 没有出边，结束旅游。
- 点 x 有 条出边，小 C 等概率地选一条边走过去。
小 J 是小 C 的好朋友，小 J 可以使用魔法让一些边消失，但是有一些限制 (x,y)：第 y 条边如果被删掉了，那么第 x 条边也会受到影响，导致 x 条边被删掉。
现在小 J 想知道，如何删边使得小 C 所经过的边数期望最大。
nleq 50,mleq 500,kleq 2000。
Solution
走到终点的期望步数，显然有：
我们很容易可以想到使用分数规划。
二分答案 mid，将所有 f 减去 mid 后跑一遍最大权闭合子图，判断是否大于 0，如果大于 0 则平均值大于 mid，反之亦然。
题目比较清新简单，数据比较卡精度，本人卡了快两个小时。
Code
代码语言：javascript复制//题出的很好，下次别出了。
#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 '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("%.14Lfn",f[1]),0;
}
