一個(gè) 深度優(yōu)先搜索以及回溯遞歸的 經(jīng)典運(yùn)用，復(fù)雜度是 ?O（NM）

需要注意的是: 選擇的 ?點(diǎn)倆倆要求 等級(jí)限制，以及一個(gè)點(diǎn)只能 應(yīng)用一次， 即使有環(huán) 也不要緊。

#include <cstring> #include <cstdio> #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) < (b) ? (b) : (a)) const int N = 105; struct Edge {int to,val,pre;Edge(){}Edge(int TO, int VAL, int PRE) : to(TO), val(VAL), pre(PRE){};void show() {printf ("%d %d %d\n", to, val, pre);} }; int head[N], pos, m, n; Edge edge[N * N]; int P[N], L[N]; bool flag[N];void init(){memset(head, -1, sizeof head);memset(flag, 0, sizeof flag);pos = 0; }void addEdge(int s, int to, int val) {edge[pos] = Edge(to, val, head[s]);head[s] = pos ++; }int dfs(int person, int left, int right) {if (L[person] + m < right || L[person] - m > left) return 0x7fffffff;flag[person] = true;int ans = P[person];for(int i = head[person]; ~i ; i = edge[i].pre) {Edge &tmp = edge[i];if (!flag[tmp.to]) {int wpd = dfs(tmp.to, min(left, L[tmp.to]), max(right, L[tmp.to]));if (wpd == 0x7fffffff) continue;wpd += tmp.val;ans = min(ans, wpd);}}flag[person] = false;return ans; }void solve() {printf("%d\n", dfs(1, L[1], L[1])); }int main() {int X, T, V;while(~scanf("%d%d", &m, &n)) {init();for(int i = 1 ; i <= n ; ++i) {scanf("%d%d%d", P + i , L + i, &X);for( int j = 1 ; j <= X ; ++j) {scanf("%d%d", &T, &V);addEdge(i, T, V);}}solve();}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/shuly/p/7273105.html

總結(jié)

以上是生活随笔為你收集整理的poj-1062-昂贵的聘礼的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。