HDU 5118 GRE Words Once More!

题目链接：HDU-5118

题意：给定一个有向无环图，每条边有一个权值。标定一些特定节点为“特殊节点”。从节点1出发到某“特殊节点”结束的路径，称为一个“GRE单词”。单词由路径上的权值组成。给定一组查询\(k_i\)，问由给定的图产生的所有单词，按字典序排序后第\(k_i\)个单词的长度（即由多少条边组成）。

思路：首先这道题最吓人之处在于\(k_i<=10^{8}\)，单纯的扫一遍所有可能出现的单词会超时。这时我们发现，输出时只要求输出单词长度，而不要求输出单词内容。由于是DAG，每个节点不会连回到祖宗节点。我们定义vis[i]为从节点i出发可以找到以“特殊节点”结尾的路径的数量。则可以得到递推关系：\(vis[u]=\sum_{V}{vis[v]}\)。同样的道理，我们记录第一次访问每个节点时，产生的所有以“特殊节点”结尾的路径。那么每个节点的子节点其实只需要遍历一次。之后访问时，直接加上之前的结果就可以了。

如果题解说的不是很明白，建议直接看代码，很容易看懂。

网上的一些题解说需要手动dfs，不过本人并没有手动也没有爆栈。建议谨慎地尝试。

 #include"bits/stdc++.h"

 using namespace std;

 typedef long long LL;

 // ans[i]为字典序第i的单词

 // vis[i]为从节点i出发能找到以“特殊节点”结尾的路径的数量

 // firstVis[i]为从节点i出发找到的"所有以“特殊节点”结尾的路径的深度"在ans中存储的起始位置

 // firstVisDep[i]为第一次访问i时的深度

 const int MAXN=;

 const int MAXM=;

 struct Edge

 {

     int u,v,w;

     Edge(int uu,int vv,int ww)

     {

         u=uu,v=vv,w=ww;

     }

     bool operator < (Edge x)

     {

         return w < x.w;

     }

 };

 vector<Edge> G[MAXN];

 int s[MAXN];

 int n,m,q;

 int sum;

 int ans[MAXM],vis[MAXN],firstVis[MAXN],firstVisDep[MAXN];

 void addEdge(int u,int v,int w)

 {

     G[u].push_back(Edge(u,v,w));

 }

 void dfs(int u,int dep)

 {

     if(sum>=) return;

     if(vis[u]!=-)

     {

         for(int i=;i<=vis[u];i++)

         {

             if(sum>=) return;

             ans[++sum]=ans[firstVis[u]+i]+dep-firstVisDep[u];

         }

         return ;

     }

     firstVis[u]=sum;

     firstVisDep[u]=dep;

     if(s[u]) ans[++sum]=dep;

     for(unsigned int i=;i<G[u].size();i++)

     {

         int v=G[u][i].v;

         dfs(v,dep+);

     }

     vis[u]=sum-firstVis[u];

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in.txt","r",stdin);

     // freopen("out.txt","w",stdout);

 #endif

     int t;

     scanf("%d",&t);

     for(int tt=;tt<=t;tt++)

     {

         scanf("%d%d%d",&n,&m,&q);

         for(int i=;i<=n;i++) G[i].clear();

         s[]=;

         for(int i=;i<=n;i++) scanf("%d",&s[i]);

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

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             addEdge(u,v,w);

         }

         for(int i=;i<=n;i++) sort(G[i].begin(),G[i].end());

         memset(vis,-,sizeof(vis));

         sum=;

         dfs(,);

         printf("Case #%d:\n",tt);

         for(int i=;i<=q;i++)

         {

             int x;

             scanf("%d",&x);

             if(x<=sum) printf("%d\n",ans[x]);

             else printf("-1\n");

         }

     }

     return ;

 }

巴特西

HDU 5118 GRE Words Once More!

最新文章

热门文章