Brief description :

给定一个单向图，边权记做 G[i][j]，终点 n 处有一个魔王。
英雄要从出发点1开始，经过迷宫，每通过一条边自己的生命值会发生改变。
（计算的公式是 Hp = (Hp*2)+G[i][j]，生命<=0 时被算做是死亡。） 求的要碰到魔王，英雄所需要的最小初始生命值。

Analyse :

两种解法，分别是从正面二分答案搜索，和一种从终点将整个过程逆向进行的方法，两种方法各有利弊，不过我认为标程是后者，所以比赛的时候写的也是。
没有注意到double的问题，而且初始值赋的也不对一直WA到比赛结束。
（应该赋值为 0 然后在计算出 3 的时候扰动一下… 而之前我赋值为 1 …）
逆向写的时候还不得不考虑的一个问题是如果中途发生死亡事件的处理。。
请参考 Relax 的地方。（这个地方值得仔细思考呀。）

对于具体搜索的过程也有许多方法可以写，从普通的搜索，或者用边目录存的Bellman，都是可过的。对于二分答案的方法，考虑到这个子程序会反复调用，另一种更好的写方是先将整个图先预处理建立出 Dag 链，
然后执行动态规划。（这个方法我是学习 Xiaodai 的。^ ^）

下面的两份代码都是用Bellman的。。。

#include 
#include 
#include 
using namespace std;
const double INF = 1e10;
const int N = 100;
struct edge{
    int a, b;
    int w;
}; vector E;
int G[N][N]; double D[N];
int n;


void relax(int u, int v){
    D[v] = max(D[v], D[u] * 2 + G[u][v]);
}

bool check(int x){
    int i, j;
    for (i=1;i0;
}

void init(){
    E.clear(); edge x;
    for (int i=0;i> G[i][j]; if (G[i][j]==0) continue;
                x.a = i; x.b = j;
                E.push_back(x);
            }
}


int main(){
    while (cin >> n){
        init(); int l = 1, r = 1e9, m;
        while (l
#include 
#include 
#include 
using namespace std;
const double INF = 1e10;
const int N = 100;
struct edge{
    int a, b;
    int w;
}; vector E;
int G[N][N];
double D[N];
int n;


void relax(int u, int v){
    double w = (D[v]-G[u][v])/2;
    D[u] = min(D[u], w); D[u] = max(D[u], .0);
}

void bellman_ford(){
    int i, j;
    for (i=0;i> G[i][j]; if (G[i][j]==0) continue;
                x.a = i; x.b = j;
                E.push_back(x);
            }
}


int main(){
    while (cin >> n){
        init(); bellman_ford();
        cout << ceil(D[0]+1e-10) << endl;
    }
}






External link :
http://acm.hit.edu.cn/judge/show.php?Proid=2853
                                                												

													Posted by 
													xiaodao													
													Category: 													日常