bzoj 4501: 旅行 01分数规划+概率期望dp
2024-09-04 16:09:37
题目大意:
题解:
首先我们不考虑可以删除边的情况下,如何计算期望边数.
然后我们发现这是个有向无环图
所以直接\(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;
}
最新文章
- HDU 2159---FATE---带限制的完全背包
- svnUbuntu下安装与使用（ZT）
- CF -- 414A
- 排序算法_HeapSort
- 用SQL替换最后一个指定字符后面的所有字符
- LInux系统的C语言开发工具笔记
- 关于Qt信号与槽机制的传递方向性研究（结论其实是错误的，但是可以看看分析过程）
- 利用XCode来进行IOS的程序开发
- HighCharts基本折线图
- (NO.00003)iOS游戏简单的机器人投射游戏成形记(七)
- java多线程系列 目录
- 【刷题】BZOJ 2151 种树
- 简明 MongoDB 入门教程
- Trie树子节点快速获取法
- 列出Windows域中所有的机器
- 如何获取e.printStackTrace()的内容
- Html5游戏开发-145行代码完成一个RPG小Demo
- Python可执行对象——exec、eval、compile
- Linux服务器性能评估与优化（二)
- cvCalcOpticalFlowPyrLK的使用--基于高斯金字塔的稀疏光流特征集求解