首页 > 代码库 > bzoj4501 旅行

bzoj4501 旅行

2024-09-06 06:44:18   217人阅读

题面:

小C来到了F国，小C想好好地参观F国。F国可以看一个有n个点m条边的有向无环图，小C刚开始站在1号点。假设现在小C站在x号点：

1．点x没有出边，结束旅游。

2．点x有o条出边，小C等概率地选一条边走过去。

小J是小C的好朋友，小J可以使用魔法让一些边消失，但是有一些限制(x,y)：第y条边如果被删掉了，那么第x条边也会受到影响，导致第x条边被删掉。

现在小J想知道，如何删边使得小C所经过的边数期望最大。

第一行三个整数，n,m,k(1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000)，代表有n个点，m条边，k个限制。

接下来m行，第i行代表第i条边x,y(1 <= x, y <= n)，方向是从x到y。

接下来k行，每行有两个整数x,y(1 <= x, y <= m)，代表限制。

保证图是有向无环的，保证对于每个限制(x,y)，第x条边和第y条边的起点是相同的。可能有重边，限制可能重复。

1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000

首先既然是有向无环图,那么如果最优决策中从点x出发的期望步数最多,且从x向y有一条边,必然从y出发的期望步数也达到最多，那么我们按拓扑序依次求出从每个点出发的期望最大步数f[x]即可.

假设我们已经知道了从x出发能到达的所有点的f值,并选择了j条边保留,那么f[x]=1+sigma{f[y],保留的某条边从x指向y}/j,每保留一条边,分子和分母都会增加,相当于保留的边指向的f值的平均值最大，相当于01分数规划,二分这个平均值即可.二分之后每条边有一个权值,如果能选出一些边使得权值和大于0说明答案大于等于当前判断的值.那么接下来跑最大权闭合子图即可.

注意最大权闭合子图的建模是不需要对SCC缩点也能跑的,NOI植物大战僵尸是因为SCC不能选所以需要缩点.我比较简单无脑缩点直接上了于是飙到170行+...不过namespace大法吼啊….被调试续了1h，最后发现我把题读错了,限制的x,y是y删了导致x一定被删不是x删了导致y被删…..新技能get:调代码调不动的时候重新读一遍题有奇效！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=1e-8;
int cmp(double x){return x<-eps?-1:x>eps;}
namespace DINIC{
  const int maxn=1005,maxm=10005;
  struct edge{
    int to,next;double w;
  }lst[maxm];int len=0,first[maxn],_first[maxn];
  void clear(){
    memset(first,-1,sizeof(first));len=0;
  }
  void addedge(int a,int b,double w){
    lst[len].to=b;lst[len].next=first[a];lst[len].w=w;first[a]=len++;
    lst[len].to=a;lst[len].next=first[b];lst[len].w=0;first[b]=len++;
  }
  int q[maxn],vis[maxn],dis[maxn],head,tail,T,s,t;
  bool bfs(){
    head=tail=0;vis[s]=++T;dis[s]=1;q[tail++]=s;
    while(head!=tail){
      int x=q[head++];
      for(int pt=first[x];pt!=-1;pt=lst[pt].next){
    if(lst[pt].w>eps&&vis[lst[pt].to]!=T){
      vis[lst[pt].to]=T;q[tail++]=lst[pt].to;dis[lst[pt].to]=dis[x]+1;
    }
      }
    }
    if(vis[t]==T)memcpy(_first,first,sizeof(first));
    return vis[t]==T;
  }
  double dfs(int x,double lim){
    if(x==t)return lim;
    double flow=0,a;
    for(int pt=_first[x];pt!=-1;pt=lst[pt].next){
      if(lst[pt].w>eps&&dis[lst[pt].to]==dis[x]+1&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))>eps){
    lst[pt].w-=a;lst[pt^1].w+=a;flow+=a;
    if(cmp(flow-lim)==0)return flow;
      }
    }
    return flow;
  }
  double dinic(){
    double ans=0,x;
    while(bfs())while((x=dfs(s,1e5))>eps)ans+=x;
    return ans;
  }
};
namespace Tarjan{
  const int maxm=2005,maxn=505;
  struct edge{
    int to,next;
  }lst[maxm],lst2[maxm];int len=1,first[maxn],len2=1,first2[maxn];
  void addedge(int a,int b){
    lst[len].to=b;lst[len].next=first[a];first[a]=len++;
  }
  void addedge2(int a,int b){
    lst2[len2].to=b;lst2[len2].next=first2[a];first2[a]=len2++;
  }
  int dfn[maxn],low[maxn],s[maxn],top,belong[maxn],tot,T;bool ins[maxn];
  void dfs(int x){
    dfn[x]=low[x]=++T;ins[x]=true;s[top++]=x;
    for(int pt=first[x];pt;pt=lst[pt].next){
      if(!dfn[lst[pt].to]){
    dfs(lst[pt].to);
    if(low[lst[pt].to]<low[x])low[x]=low[lst[pt].to];
      }else if(ins[lst[pt].to]&&dfn[lst[pt].to]<low[x])low[x]=dfn[lst[pt].to];
    }
    if(dfn[x]==low[x]){
      ++tot;
      do{
    ins[s[--top]]=false;belong[s[top]]=tot;
      }while(s[top]!=x);
    }
  }
  void tarjan(int n,int m){
    int x,y;
    for(int i=1;i<=m;++i){
      scanf("%d%d",&x,&y);addedge(x,y);//选x必须选y
    }
    for(int i=1;i<=n;++i){
      if(!dfn[i])dfs(i);
    }
    for(int i=1;i<=n;++i){
      for(int pt=first[i];pt;pt=lst[pt].next){
    if(belong[i]!=belong[lst[pt].to]){
      addedge2(belong[i],belong[lst[pt].to]);
    }
      }
    }
  }
};
namespace Main{
  const int maxm=505,maxn=55;
  int n,m,k;
  struct edge{
    int to,next,num;
  }lst[maxm];int len=1,first[maxn];
  void addedge(int a,int b,int i){
    lst[len].to=b;lst[len].next=first[a];lst[len].num=i;first[a]=len++;
  }
  int sz[maxm];
  bool vis[maxn];
  double f[maxn];
  double sum[maxm];
  int scc[maxm];int tot=0;
  int sccused[maxm],T;
  bool check(double ans){
    DINIC::clear();using DINIC::addedge;using DINIC::s;using DINIC::t;
    s=0;t=m+1;
    double ori=0;
    for(int i=1;i<=tot;++i){
      int x=scc[i];
      if(cmp(sum[x]-ans*sz[x])>=0){
    addedge(s,x,sum[x]-ans*sz[x]);ori+=sum[x]-ans*sz[x];
      }
      else addedge(x,t,ans*sz[x]-sum[x]);
    }
    using Tarjan::first2;using Tarjan::lst2;
    for(int i=1;i<=tot;++i){
      for(int pt=first2[scc[i]];pt;pt=lst2[pt].next){
    addedge(scc[i],lst2[pt].to,1e5);
      }
    }
    return cmp(ori-DINIC::dinic())>0;
  }
  void getf(int x){
    using Tarjan::belong;
    if(!first[x])f[x]=0;
    else{
      tot=0;++T;
      for(int pt=first[x];pt;pt=lst[pt].next){
    sum[belong[lst[pt].num]]+=f[lst[pt].to];
    sz[belong[lst[pt].num]]++;
    if(sccused[belong[lst[pt].num]]!=T){
      sccused[belong[lst[pt].num]]=T;scc[++tot]=belong[lst[pt].num];
    }
      }
      double l=0,r=55;
      while(r-l>1e-8){
    double mid=(l+r)/2.0;
    if(check(mid))l=mid;
    else r=mid;
      }
      f[x]=l+1;
    }
  }
  void dfs(int x){
    vis[x]=true;
    for(int pt=first[x];pt;pt=lst[pt].next){
      if(!vis[lst[pt].to])dfs(lst[pt].to);
    }
    getf(x);
  }
  void work(){
    scanf("%d%d%d",&n,&m,&k);
    int x,y;
    for(int i=1;i<=m;++i){
      scanf("%d%d",&x,&y);addedge(x,y,i);
    }
    Tarjan::tarjan(m,k);
    for(int i=1;i<=n;++i){
      if(!vis[i])dfs(i);
    }
    printf("%.10f\n",f[1]);
  }
};
int main(){
  Main::work();
  return 0;
}

 

bzoj4501 旅行


联系
我们