题目大意:
题解:
首先我们不考虑可以删除边的情况下,如何计算期望边数.
然后我们发现这是个有向无环图
所以直接\(f[u] = \sum\frac{f[v] + 1}{deg_u}\)直接计算即可
然后我们考虑如果允许删除边
注意这句话
保证对于每个限制(x,y)，第x条边和第y条边的起点是相同的
所以可以分别考虑每次转移
这时候我们考虑如何决策才能最优化\(f[u]\)
即最优化\(\sum\frac{f[v] + 1}{deg_u}\)
将式子变形:\(\frac{\sum(f[v] + 1)x_i}{\sum x_i}\)
我们发现这是一个分式,所以可以利用01分数规划来最大化取值
所以我们有\(f(L) = \sum d_ix_i > 0\)时存在更优值,\(d_i = (f_i + 1) - L\)
所以利用01分数规划,问题转化成了最大化\(\sum d_ix_i\)
这个问题可以转化为一个最小割模型(最大权闭合子图),跑网络流即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxm = 512;
const int maxk = 2048;
const double eps = 1e-6;
const double inf = 1e8;
namespace net{
struct Edge{
int to,next;
double cap;
}G[(maxk<<1) + (maxm<<1) + 1010];
int head[(maxm<<1) + 100],cnt = 1;
void add(int u,int v,double d){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
G[cnt].cap = d;
}
inline void insert(int u,int v,double d){
add(u,v,d);add(v,u,0);
}
#define v G[i].to
int q[(maxm<<1) + 100],l,r;
int dis[(maxm<<1) + 100],S,T;
bool bfs(){
memset(dis,-1,sizeof dis);
l = 0;r = -1;q[++r] = S;
dis[S] = 0;
while(l <= r){
int u = q[l++];
for(int i = head[u];i;i=G[i].next){
if(dis[v] == -1 && G[i].cap > eps){
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}
return dis[T] != -1;
}
double dfs(int u,double f){
if(u == T || f < eps) return f;
double ret = 0;
for(int i = head[u];i;i=G[i].next){
if(dis[v] == dis[u] + 1 && G[i].cap > eps){
double x = dfs(v,min(G[i].cap,f));
ret += x;f -= x;
G[i].cap -= x;
G[i^1].cap += x;
if(f < eps) break;
}
}
return ret;
}
#undef v
void clear(){
memset(head,0,sizeof head);cnt = 1;
S = (maxm<<1) - 5;T = S + 1;
}
double main(){
double ret = 0;
while(bfs()){
ret += dfs(S,inf);
}return ret;
}
}
namespace dp0{
struct Edge{
int to,next;
}G[maxm<<1],lim[maxk<<1];
int head[maxm],edli[maxm<<1];
int cnt,ct;
void add_ed(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
void add_li(int u,int v){
lim[++ct].to = v;
lim[ct].next = edli[u];
edli[u] = ct;
}
double d[maxm],f[maxm];
inline bool check(int u,double mid,int fa){
net::clear();
double total = .0;
for(int i = head[u];i;i=G[i].next){
if(G[i].to == fa) continue;
d[i] = f[G[i].to] - mid + 1;
if(d[i] > eps){
total += d[i];
net::insert(i,net::T,d[i]);
}else if(d[i] < -eps){
net::insert(net::S,i,-d[i]);
}
for(int v = edli[i];v;v=lim[v].next){
net::insert(i,lim[v].to,inf);
}
}
total -= net::main();
return total > eps;
}
inline double work(int u,int fa){
double l = .0,r = inf;
while(r-l > eps){
double mid = (l+r)/2.0;
if(check(u,mid,fa)) l = mid;
else r = mid;
}return l;
}
#define v G[i].to
void dfs(int u,int fa){
if(head[u] == 0) return;
if(f[u] > eps) return;
f[u] = .0;
for(int i = head[u];i;i = G[i].next){
if(v == fa) continue;
dfs(v,u);
}
f[u] = work(u,fa);
return ;
}
#undef v
int main(){
int n,m,k;read(n);read(m);read(k);
for(int i=1,u,v;i<=m;++i){
read(u);read(v);
add_ed(u,v);
}
for(int i=1,u,v;i<=k;++i){
read(u);read(v);
add_li(v,u);
}
dfs(1,0);
printf("%.12lf\n",f[1]);
return 0;
}
}
int main(){
dp0::main();
getchar();getchar();
return 0;
}