01分数规划+最大权闭合子图
倒拓扑序处理每个节点
$$f[x]=\frac{\sum{f[v]}}{n}+1$$
二分答案$val$
只需要判断是否存在$\sum{f[v]}+1-val>0$即可
点权下放给边，限制${x,y}$即为若边$x$存在，则边$y$存在
建图，跑网络流即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define inf 0x7fffffff
#define eps 1e-7
using namespace std; namespace network{
const int N = ;
const int S = ;
const int T = ;
int e=,head[N];
struct edge{
int u,v,next;
double f;
}ed[];
void add(int u,int v,double f){
ed[e].u=u;ed[e].v=v;ed[e].f=f;
ed[e].next=head[u];head[u]=e++;
ed[e].u=v;ed[e].v=u;ed[e].f=;
ed[e].next=head[v];head[v]=e++;
}
int dep[N];
int q[N],h,t;
bool bfs(){
memset(dep,-,sizeof dep);
dep[S]=; h=t=; q[]=S;
while(h<=t){
int x=q[h++];
for(int i=head[x];i;i=ed[i].next){
if(ed[i].f&&dep[ed[i].v]==-){
dep[ed[i].v]=dep[x]+;
q[++t]=ed[i].v;
}
}
}
return dep[T]!=-;
}
double dfs(int x,double f){
if(x==T||f==)return f;
double ans=;
for(int i=head[x];i;i=ed[i].next){
if(ed[i].f&&dep[ed[i].v]==dep[x]+){
double nxt=dfs(ed[i].v,min(f,ed[i].f));
ed[i].f-=nxt; ed[i^].f+=nxt;
f-=nxt; ans+=nxt;
if(f==)break;
}
}
if(ans==)dep[x]=-;
return ans;
}
double dinic(){
double ans=;
while(bfs())ans+=dfs(S,inf);
return ans;
}
void init(){memset(head,,sizeof head);e=;}
} namespace graph{
const int N =;
int e=,head[N],out[N];
vector<int> lim[N];
bool vis[N];
double f[N];
struct edge{
int u,v,next;
}ed[*N];
void add(int u,int v){
ed[e].u=u;ed[e].v=v;
ed[e].next=head[u];
head[u]=e++;out[u]++;
}
bool check(int x,double y){
network::init();
double sum=;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
double val=f[v]+-y;
sum+=max(val,(double));
if(val>)network::add(network::S,i,val);
else network::add(i,network::T,-val);
for(int j=;j<lim[i].size();j++)
network::add(i,lim[i][j],(double)inf);
}
return sum-network::dinic()>;
}
double solve(int x){
if(!out[x])return 0.0;
double l=,r=,mid,ans;
for(int i=head[x];i;i=ed[i].next)
r=max(r,f[ed[i].v]+);
while(r-l>=eps){
mid=(l+r)/2.0;
if(check(x,mid))l=ans=mid;
else r=mid;
}
return ans;
}
void work(int x){
for(int i=head[x];i;i=ed[i].next)
if(!vis[ed[i].v]){
work(ed[i].v);
vis[ed[i].v]=;
}
f[x]=solve(x);
}
} int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
graph::add(u,v);
}
for(int i=,x,y;i<=k;i++){
scanf("%d%d",&x,&y);
graph::lim[x].push_back(y);
}
graph::work();
printf("%lf\n",graph::f[]);
}
/*
3 3 1
1 2
1 3
2 3
1 2
*/