HDU 4889 Scary Path Finding Algorithm

其实这个题是抄的题解啦…… 题解给了一个图，按照那个图模拟一遍大概就能理解了。

题意：

　　有一段程序，给你一个C值(程序中某常量)，让你构造一组数据，使程序输出"doge"
　　那段代码大概是 SPFA的SLF优化。其实题目的意思是让我们构造一组数据，使得总的出队次数大于C。
数据范围 C<=23,333,333。输出的图中最多有100个点，没有重边、自环、负环。

思路：

　　SLF: 设队首元素为 i, 队列中要加入节点 j, 在时加到队首而不是队尾, 否则和普通的 SPFA 一样加到队尾.

　　这个优化是基于贪心的思想，因为出当前结点的的距离越小，那么他可能更新点就越多，从而达到优化的目的。

　　因为是贪心，我们可以“欺骗”他一下。
我们可以让距离比较大的结点加入队列，那么他会比较晚出队，但是，他会经过一系列的会更新原来更新过的结点，那么被更新的点会重新入队。那么被更新点原来的更新路径会重新被更新一次。

题解：来自这里

代码：先在程序中把图建出来，然后在输出图。这样做会简单一些。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <functional>

 #include <time.h>

 using namespace std;

 const int INF = <<;

 const int MAXN = ;

 int myPow(int d, int n) {

     int res = ;

     while (n>) {

         if (n&) res *= d;

         d *= d;

         n >>= ;

     }

     return res;

 }

 vector<pair<int, int> > G[MAXN];

 int n, m;

 void getGraph() {

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

         G[i].clear();

     n = ;

     for (int i = ; i >= ; i--) {

         G[n].push_back(make_pair(n+, ));

         G[n].push_back(make_pair(n+, (i!=) ? (-myPow(, i-)) : ));

         G[n+].push_back(make_pair(n+, -myPow(, i)));

         n += ;

     }

     m = ;

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

         m += G[i].size();

 }

 void output() {

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

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

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

             printf("%d %d %d\n", i, G[i][j].first, G[i][j].second);

 }

 int main() {

     #ifdef Phantom01

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

     #endif //Phantom01

     getGraph();

     int C;

     while (scanf("%d", &C)!=EOF) {

         output();

     }

     return ;

 }

巴特西

HDU 4889 Scary Path Finding Algorithm

最新文章

热门文章