01分数规划+最大权闭合子图 

倒拓扑序处理每个节点 

$$f[x]=\frac{\sum{f[v]}}{n}+1$$

二分答案$val$

只需要判断是否存在$\sum{f[v]}+1-val>0$即可 

点权下放给边，限制${x,y}$即为若边$x$存在，则边$y$存在 

建图，跑网络流即可

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #define inf 0x7fffffff 8 #define eps 1e-7 9 using namespace std; 10 11 12 namespace network{ 13 const int N = 1005; 14 const int S = 1001; 15 const int T = 1002; 16 int e=2,head[N]; 17 struct edge{ 18 int u,v,next; 19 double f; 20 }ed[310000]; 21 void add(int u,int v,double f){ 22 ed[e].u=u;ed[e].v=v;ed[e].f=f; 23 ed[e].next=head[u];head[u]=e++; 24 ed[e].u=v;ed[e].v=u;ed[e].f=0; 25 ed[e].next=head[v];head[v]=e++; 26 } 27 int dep[N]; 28 int q[N],h,t; 29 bool bfs(){ 30 memset(dep,-1,sizeof dep); 31 dep[S]=1; h=t=1; q[1]=S; 32 while(h<=t){ 33 int x=q[h++]; 34 for(int i=head[x];i;i=ed[i].next){ 35 if(ed[i].f&&dep[ed[i].v]==-1){ 36 dep[ed[i].v]=dep[x]+1; 37 q[++t]=ed[i].v; 38 } 39 } 40 } 41 return dep[T]!=-1; 42 } 43 double dfs(int x,double f){ 44 if(x==T||f==0)return f; 45 double ans=0; 46 for(int i=head[x];i;i=ed[i].next){ 47 if(ed[i].f&&dep[ed[i].v]==dep[x]+1){ 48 double nxt=dfs(ed[i].v,min(f,ed[i].f)); 49 ed[i].f-=nxt; ed[i^1].f+=nxt; 50 f-=nxt; ans+=nxt; 51 if(f==0)break; 52 } 53 } 54 if(ans==0)dep[x]=-1; 55 return ans; 56 } 57 double dinic(){ 58 double ans=0; 59 while(bfs())ans+=dfs(S,inf); 60 return ans; 61 } 62 void init(){memset(head,0,sizeof head);e=2;} 63 } 64 65 66 namespace graph{ 67 const int N =505; 68 int e=1,head[N],out[N]; 69 vector
             
               lim[N]; 70 bool vis[N]; 71 double f[N]; 72 struct edge{ 73 int u,v,next; 74 }ed[2*N]; 75 void add(int u,int v){ 76 ed[e].u=u;ed[e].v=v; 77 ed[e].next=head[u]; 78 head[u]=e++;out[u]++; 79 } 80 bool check(int x,double y){ 81 network::init(); 82 double sum=0; 83 for(int i=head[x];i;i=ed[i].next){ 84 int v=ed[i].v; 85 double val=f[v]+1-y; 86 sum+=max(val,(double)0); 87 if(val>0)network::add(network::S,i,val); 88 else network::add(i,network::T,-val); 89 for(int j=0;j
              
               0; 93 } 94 double solve(int x){ 95 if(!out[x])return 0.0; 96 double l=0,r=0,mid,ans; 97 for(int i=head[x];i;i=ed[i].next) 98 r=max(r,f[ed[i].v]+1); 99 while(r-l>=eps){100 mid=(l+r)/2.0;101 if(check(x,mid))l=ans=mid;102 else r=mid;103 }104 return ans;105 }106 void work(int x){107 for(int i=head[x];i;i=ed[i].next)108 if(!vis[ed[i].v]){109 work(ed[i].v);110 vis[ed[i].v]=1;111 }112 f[x]=solve(x);113 }114 }115 116 int main(){117 int n,m,k;118 scanf("%d%d%d",&n,&m,&k);119 for(int i=1,u,v;i<=m;i++){120 scanf("%d%d",&u,&v);121 graph::add(u,v);122 }123 for(int i=1,x,y;i<=k;i++){124 scanf("%d%d",&x,&y);125 graph::lim[x].push_back(y);126 }127 graph::work(1);128 printf("%lf\n",graph::f[1]);129 }130 /*131 3 3 1132 1 2133 1 3134 2 3135 1 2136 */