bzoj4501: 旅行
链接
思路
我居然一上来就的去重边，我tm真可爱。
如果没有修改的话就是一个拓扑dp。
(f[u]=sumfrac{f[v]+1}{numson})
修改的话a[i]表示这个边要不要。
(f[u]=frac{sum (f[v]+1)*a[i]}{sum a[i]})
第x条边和第y条边的起点是相同的
所以我们拓扑是不会影响的。
所以只要拓扑考虑每个节点最大就好了。
(f[u]=frac{sum (f[v]+1)*a[i]}{sum a[i]})
分母很丑，换一下
(sum a[i]*f[u]=sum (f[v]+1)*a[i])
(sum a[i]*f[u]-sum (f[v]+1)*a[i]=0)
(sum a[i](f[u]-f[v]-1)=0)
然后我们二分答案f[u]。
判定(sum a[i](f[u]-f[v]-1)<0)
这是普通01分数规划的过程。
如何check使得(sum a[i](f[u]-f[v]-1))最大？
(其实是(sum a[i](f[v]+1-f[u]))最大，不过都一样啦)
第y条边如果被删掉了，那么第x条边也会受到影响，导致x条边被删掉。
就是选x就要选y，可以用最大权闭合子图求,别和我扯2-sat
正权和-最小割
细节
网络流的节点是边的编号。
虽然最终答案精度只要小于(1e-2)就行。但是eps还是要开大点(1e-9)，误差会叠加。
这是有重边的，不要queue去拓扑了，dfs拓扑。
还有，我的网络流板子居然wrong了、、、
代码
#include <bits/stdc++.h>
#define iter vector<int>::iterator
#define iter_Pair vector<pair<int,int> >::iterator
#define eps 1e-9
#define inf 0x7fffffff
using namespace std;
const int N=1007;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
double f[N];
int n,m,k,S,T;
vector<pair<int,int> > xianzhi[N];
pair<int,int> edge[N];
namespace flow {
struct node {
int v,nxt;
double cap;
}e[N<<5];
int head[N],dis[N],tot;
void clear() {
memset(head,0,sizeof(head));
tot=1;
}
void add_edge(int u,int v,double cap) {
e[++tot].v=v;
e[tot].cap=cap;
e[tot].nxt=head[u];
head[u]=tot;
}
void add(int u,int v,double cap) {
add_edge(u,v,cap),add_edge(v,u,0.0);
}
bool bfs() {
memset(dis,-1,sizeof(dis));
queue<int> q;
q.push(S);
dis[S]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(dis[v]==-1&&e[i].cap) {
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[T]!=-1;
}
double dfs(int u,double f) {
if(u==T) return f;
double ans=0;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].cap&&f) {
double t=dfs(v,min(e[i].cap,f));
e[i].cap-=t,e[i^1].cap+=t;
f-=t,ans+=t;
}
}
return ans;
}
double dinic() {
double ans=0;
while(bfs()) ans+=dfs(S,inf);
return ans;
}
}
struct node {
int v,nxt,q;
}e[N];
int head[N],tot;
void add(int u,int v) {
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
bool check(int u,double mid) {
flow::clear();
double sum=0;
for(iter_Pair it=xianzhi[u].begin();it!=xianzhi[u].end();++it)
flow::add(it->first,it->second,inf);
for(int i=head[u];i;i=e[i].nxt) {
double w=1+f[e[i].v]-mid;
if(w>0) flow::add(S,i,w),sum+=w;
else flow::add(i,T,-w);
}
sum-=flow::dinic();
return sum>0;
}
void calc(int u) {
double l=0,r=0;
for(int i=head[u];i;i=e[i].nxt) r=max(r,f[e[i].v]+1);
while(r-l>=eps) {
double mid=(l+r)/2.0;
if(check(u,mid)) f[u]=l=mid;
else r=mid;
}
}
int vis[N];
void tuopu(int u) {
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!vis[v]) tuopu(v);
}
calc(u);
}
int main() {
n=read(),m=read(),k=read();
for(int i=1;i<=m;++i) {
int u=read(),v=read();
edge[i]=make_pair(u,v);
add(u,v);
}
S=1000+1,T=1000+2;
for(int i=1;i<=k;++i) {
int x=read(),y=read();
if(x==y) continue;
xianzhi[edge[x].first].push_back(make_pair(x,y));
}
tuopu(1);
printf("%.6lf
",f[1]);
return 0;
}