[POI2007]Tourist Attractions

题目大意：
　　给你一个$n(n\leq 2\times 10^4)$个点，$m(m\leq 2\times 10^5)$条边的带边权的连通图。其中有$k(k\leq 20)$个关键点。关键点之间有$g$条拓扑结构的依赖关系，每条依赖关系$(u,v)$描述点$v$依赖于点$u$，即点$u$必须在点$v$之前出现。若同时存在依赖关系$(u,v)$和$(v,w)$，则有依赖关系$(u,w)$。每个点可以经过多次，经过的可以不满足依赖关系。求一条从$1$到$n$的最短的路径，满足每个关键点至少有一次被经过时满足了依赖关系。

思路：
　　状压DP。
　　首先用Floyd预处理每个关键点依赖的点集$pre[i]$。然后用Dijkstra求出点$1$和每个关键点作为起点的单源最短路。
　　用$f[S][i]$表示已满足依赖关系的点集为$S$，当前路径上，最后一个结点为$i$。
　　预处理$f[i][i]=\left\{\begin{aligned}dis[1][i]&&{pre[i]=\varnothing}\\\infty&&pre[i]\neq\varnothing\end{aligned}\right.$。
　　转移方程为$f[S\bigcup i][i]=\min\{f[S][j]+dis[i][j]\mid i\notin S\land pre[i]\in S\}$。
　　答案$ans=\min{f[U][i]+dis[i][n]}$。
　　Floyd$O(k^3)$，配对堆优化Dijkstra$O(m+n\log n)$，动态规划$O(2^kk^2)$时间复杂度为$O(k^3+m+n\log n+2^kk^2)$。空间复杂度$O(2^kk)$。
　　在BZOJ上跑了9068 MS，内存89980 KB，Rank 2。但是POI原题内存是64 MB。
　　一种卡内存的方法是压缩一下状态，因为$f[S][i]$中$S$一定包括$i$，因此我们可以把$i$这一位去掉，然后把大于$i$的位往前移。空间除以一个常数，可以卡过。
　　还有一种做法是根据$S$中元素个数，将DP数组进行滚动，空间复杂度为$O(n\binom{k}{\lceil\frac{k}{2}\rceil})$。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 #include<climits>

 #include<functional>

 #include<ext/pb_ds/priority_queue.hpp>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,K=;

 const int inf=INT_MAX;

 struct Edge {

     int to,w;

 };

 std::vector<Edge> e[N];

 inline void add_edge(const int &u,const int &v,const int &w) {

     e[u].push_back((Edge){v,w});

     e[v].push_back((Edge){u,w});

 }

 bool b[K][K];

 int n,m,k,pre[K],dis0[N],dis[K][N],f[<<K][K];

 struct Vertex {

     int id,dis;

     bool operator > (const Vertex &another) const {

         return dis>another.dis;

     }

 };

 void dijkstra(const int &s,int dis[]) {

     static __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;

     static __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[N];

     for(register int i=;i<=n;i++) {

         p[i]=q.push((Vertex){i,dis[i]=i==s?:inf});

     }

     while(!q.empty()) {

         const int x=q.top().id;

         q.pop();

         for(register unsigned i=;i<e[x].size();i++) {

             const int &y=e[x][i].to,&w=e[x][i].w;

             if(dis[x]+w<dis[y]) {

                 q.modify(p[y],(Vertex){y,dis[y]=dis[x]+w});

             }

         }

     }

 }

 int main() {

     n=getint(),m=getint(),k=getint();

     for(register int i=;i<m;i++) {

         const int u=getint(),v=getint(),w=getint();

         add_edge(u,v,w);

     }

     if(k==) {

         dijkstra(,dis0);

         printf("%d\n",dis0[n]);

         return ;

     }

     for(register int i=getint();i;i--) {

         const int u=getint(),v=getint();

         b[u-][v-]=true;

     }

     for(register int l=;l<k;l++) {

         for(register int i=;i<k;i++) {

             if(i==l||!b[i][l]) continue;

             for(register int j=;j<k;j++) {

                 if(j==l||j==i||!b[l][j]) continue;

                 b[i][j]=true;

             }

         }

     }

     for(register int i=;i<k;i++) {

         for(register int j=;j<k;j++) {

             if(b[i][j]) pre[j]|=<<i;

         }

     }

     dijkstra(,dis0);

     for(register int i=;i<=k+;i++) {

         dijkstra(i,dis[i-]);

     }

     for(register int state=;state<<<k;state++) {

         for(register int i=;i<k;i++) {

             f[state][i]=inf;

         }

     }

     for(register int i=;i<k;i++) {

         if(!pre[i]) f[<<i][i]=dis0[i+];

     }

     for(register int state=;state<<<k;state++) {

         for(register int i=;i<k;i++) {

             if(!(state&(<<i))&&(state&pre[i])==pre[i]) {

                 for(register int j=;j<k;j++) {

                     if(f[state][j]!=inf) {

                         f[state^(<<i)][i]=std::min(f[state^(<<i)][i],f[state][j]+dis[j][i+]);

                     }

                 }

             }

         }

     }

     int ans=inf;

     for(register int i=;i<k;i++) {

         if(f[(<<k)-][i]==inf) continue;

         ans=std::min(ans,f[(<<k)-][i]+dis[i][n]);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

[POI2007]Tourist Attractions

最新文章

热门文章