大于等于 clear printf push_back 等于 node const pac
https://vjudge.net/problem/HDU-3440
题意:
一个超人,他可以一个从一栋楼跳到另一栋楼。有一天,他为了加强技能,准备跳一系列的楼,他每次都从低的楼,跳到高的楼。他从最低的楼开始跳,但是他跳的水平距离是有限制的。
但是因为他是超人,所以他可以任意移动楼,而且他想他开始跳的楼与最后跳到的楼的距离最大。
他移动楼的时候有某些限制:
1. 移动之后的楼的排列顺序必须与输入的顺序相同。
2. 必须满足水平跳跃的距离的限制。
求这个最大距离,如果跳不到的话,输出 - 1。
思路:
首先,超人跳的每栋楼的是按照高度递增的顺序来的,比如说 i,j 是高度相邻的两栋楼,那么两栋楼之间的距离肯定得满足 | xi - xj| <= d(限制),然后因为每栋楼之间的距离肯定是大于等于 1 的,所以 Xi+1 - Xi>= 1,所以我们就可以找出一系列的不等式。我们需要通过这一系列的不等式找出加入最低的下标为 u,最高的下标为 v,那么就是 | Xu-Xv | 的最大值,这样的问题其实是一类叫做差分约束系统的问题。
差分约束系统是由最短路的松弛条件 d[v] >= d[u] + w(u,v) 得来的,假设有不等式 Xi - Xj <= len,变形得到 Xi <= Xj + len,这样就和最短路的松弛条件近似了,虽然说一个是大于等于,一个是小于等于,但是本质其实是一样的,可以看成 d[i] <= d[j] + w(j,i),那么此时就可以建一条从 j 到 i 的边,然后求出目标不等式的最大值,即相当于求图中的最短路。
为什么是最短路呢?比如有 a - b <= 3 ,b - c <= 5,a - c <= 10,此时如果要求 a - c 的最大值,可以轻易地看出最大值是 8,即是图中的 a 到 c 的最短路,而不是 10,本质是求所有不等式的交集,按照差分的约束条件 <= ,那么就是求最小的那个。
还剩一个问题就是有没有可能出现无解的情况,那就是图中出现了负环,最短路可以无穷小,此时当然就无解了,比如 b - a <= -3,c - b <= 2 ,a - c <= -5,那么此时就是一个负环,此时求 c - a 的最小值,有 c - a <= -1,c - a>= 5,此时就矛盾了,不存在最小值。
ok,回过来看这道题,根据题中的 | xi - xj| <= d,我们可以建图,去掉绝对值的方法就是边从下标小的点指向下标大的点,因为输入的楼之间是有先后顺序的,之后因为每栋楼之间的距离必须大于等于 1,所以 Xi+1 - Xi>= 1(上面提到了,之后跑图的话,就用 spfa,因为 dij 无法判断途中是否存在负环,spfa 判断途中是否存在负环的条件是一个点入队的次数大于了 n。
代码:
- #include <stdio.h>
- #include <string.h>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std;
- struct edge
- {
- int from,to;
- int w;
- edge(){};
- edge(int x,int y,int z)
- {
- from = x;
- to = y;
- w = z;
- }
- };
- struct node
- {
- int hei;
- int id;
- bool operator < (const node &rhs) const
- {
- return this -> hei < rhs.hei;
- }
- } h[1005];
- vector<edge> edges;
- vector<int> v[1005];
- void init(int n)
- {
- edges.clear();
- for (int i = 0;i <= n;i++)
- v[i].clear();
- }
- void adde(int from,int to,int w)
- {
- edge e = edge(from,to,w);
- edges.push_back(e);
- int sz = edges.size();
- v[from].push_back(sz - 1);
- }
- bool vis[1005];
- int d[1005];
- int cnt[1005];
- const int inf = 0x3f3f3f3f;
- bool spfa(int s,int n)
- {
- memset(vis,0,sizeof(vis));
- memset(d,inf,sizeof(d));
- memset(cnt,0,sizeof(cnt));
- vis[s] = 1;
- cnt[s] = 1;
- queue<int> q;
- q.push(s);
- d[s] = 0;
- while (!q.empty())
- {
- int cur = q.front();
- q.pop();
- vis[cur] = 0;
- for (int i = 0;i < v[cur].size();i++)
- {
- int id = v[cur][i];
- int to = edges[id].to;
- if (d[to] > d[cur] + edges[id].w)
- {
- d[to] = d[cur] + edges[id].w;
- if (!vis[to])
- {
- q.push(to);
- vis[to] = 1;
- cnt[to]++;
- if (cnt[to] > n) return 1;
- }
- }
- }
- }
- return 0;
- }
- int main()
- {
- int t;
- int cas = 0;
- scanf("%d",&t);
- while (t--)
- {
- printf("Case %d: ",++cas);
- int n,dis;
- scanf("%d%d",&n,&dis);
- init(n);
- for (int i = 1;i <= n;i++)
- {
- scanf("%d",&h[i].hei);
- h[i].id = i;
- }
- for (int i = 1;i < n;i++)
- {
- adde(i+1,i,-1);
- }
- sort(h+1,h+n+1);
- for (int i = 1;i < n;i++)
- {
- int x = min(h[i].id,h[i+1].id);
- int y = max(h[i].id,h[i+1].id);
- adde(x,y,dis);
- }
- int s = min(h[1].id,h[n].id);
- int en = max(h[1].id,h[n].id);
- bool f = spfa(s,n);
- if (f) printf("-1\n");
- else printf("%d\n",d[en]);
- }
- return 0;
- }
hdu 3440 House Man
来源: http://www.bubuko.com/infodetail-2275799.html