YbtOJ 581「网络流」图上旅行

(Updated: )
oi
, , , , , ,

题目链接：YbtOJ #581

小 C 来到了 F 国，小 C 想好好地参观 F 国。F 国可以看一个有 $n$ 个点 $m$ 条边的有向无环图，小 C 刚开始站在 $1$ 号点。

假设现在小 C 站在 $x$ 号点：

  1. 点 $x$ 没有出边，结束旅游。
  2. 点 $x$ 有 条出边，小 C 等概率地选一条边走过去。

小 J 是小 C 的好朋友，小 J 可以使用魔法让一些边消失，但是有一些限制 $(x,y)$：第 $y$ 条边如果被删掉了，那么第 $x$ 条边也会受到影响，导致 $x$ 条边被删掉。

现在小 J 想知道，如何删边使得小 C 所经过的边数期望最大。

$n\leq 50,m\leq 500,k\leq 2000$。

Solution

不妨设 $f_i$ 表示从 $i$ 走到终点的期望步数，显然有：
$$
f_u = 1 + \frac{\sum_{<u,v>}f_v}{d_u}
$$
要使 $f_u$ 最大，则 $\frac{\sum_{<u,v>}f_v}{d_u}$ 最大，也就是平均数最大。

我们很容易可以想到使用分数规划。

二分答案 $mid$，将所有 $f$ 减去 $mid$ 后跑一遍最大权闭合子图，判断是否大于 $0$，如果大于 $0$ 则平均值大于 $mid$，反之亦然。

题目比较清新简单，数据比较卡精度，本人卡了快两个小时。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//题出的很好，下次别出了。
#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;
}