图论/最短路径

pku3072：题目大意，给定n个点，求一个机器人从点1到点n的最少用时，机器人每步走过的距离不能超过r，沿着某个方向到达一个点后，如果想到达另一个点，那么需要转过一定的角度朝向那个点才行（可能转过0度）。

解法：最短路径DP，令dis[v][u]表示从起点1经过某些顶点后到达u，再到达v的最短用时，则dis[v][u] = Min{d[v][u], dis[u][j]+map[u][v]+turnDis(p[j], p[u], p[v])}。

方程比较简单，关键是turnDis(p[j],p[u],p[v])怎么算，也就是说转过的角度。我是这么做的，假设p[j]->p[u]形成向量(x1,y1)，p[u]->p[v]形成向量(x2,y2)，那么向量夹角为atan2(y2,x2)-atan2(y1,x1)，不过这样算出的夹角可能大于pi，这个时候取2*pi-(atan2(y2,x2)-atan2(y1,x1))就可以了。

测试数据地址：http://ai.stanford.edu/~chuongdo/acm/2006/
View Code

#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <cstring>usingnamespace std;constint N =25;constdouble eps = 1e-6;constdouble pi = acos(-1);struct node{    double x, y;}p[N];int n;double r, dis[N][N], map[N][N];bool visit[N];queue <int> q;double Dis(const node &a, const node &b){    double x, y;    x = b.x - a.x;    y = b.y - a.y;    return  sqrt(x*x+y*y);}int dbcmp(double x){    if(x > eps)  return1;    elseif(x <-eps)  return-1;    elsereturn0;}double turnDis(node p0, node p1, node p2){    double x1, y1, x2, y2, tmp;    x1 = p1.x - p0.x;    y1 = p1.y - p0.y;    x2 = p2.x - p1.x;    y2 = p2.y - p1.y;    //double tmp1 = atan2(y2, x2);    //double tmp2 = atan2(y1, x1);    tmp = fabs(atan2(y2,x2)-atan2(y1,x1));    if(tmp > pi)  tmp =2*pi-tmp;    return  tmp*180.0/pi;}void spfa(){    int u, i, j;    double tmp;    while(!q.empty())  q.pop();    q.push(1);    memset(visit, false, sizeof(visit));    while(!q.empty())    {        u = q.front();        q.pop();        visit[u] =false;        for(i =1; i <= n; i++)            if(i!=u && dbcmp(map[u][i]-r)<=0)                for(j =0; j <= n; j++)                {                    if(j==0&& u!=1)  continue;                    if(j!=i && dbcmp(dis[u][j]) >=0)                    {                        tmp = turnDis(p[j],p[u],p[i]);                        if(dis[i][u]<0|| dbcmp(dis[i][u]-(dis[u][j]+tmp+map[u][i]))>0)                        {                            dis[i][u] = dis[u][j]+tmp+map[u][i];                            if(!visit[i])                            {                                q.push(i);                                visit[i] =true;                            }                        }                    }                }    }}int main(){    int i, j;    double ans;    while(scanf("%lf%d", &r, &n) != EOF)    {        if(n ==-1)  break;        for(i =1; i <= n; i++)  scanf("%lf%lf", &p[i].x, &p[i].y);        p[0].x = p[1].x-(p[n].x-p[1].x);        p[0].y = p[1].y-(p[n].y-p[1].y);        for(i =1; i <= n; i++)            for(j =0; j <= n; j++)            {                dis[j][i] =-1.0;                map[i][j] = Dis(p[i], p[j]);            }        dis[1][0] =0;        spfa();        ans =-1.0;        for(j =1; j < n; j++)            if(dbcmp(dis[n][j])>=0&& (ans<0|| dbcmp(ans-dis[n][j])>0))                ans = dis[n][j];        if(ans <0)  printf("impossiblen");        else  printf("%.0fn", ans);    }    return0;}

pku3662：题目大意，给定一个无向加权图，求从顶点1到顶点n的一条路径，其中有k条边的费用可以给你报销，求使不能被报销的边的最大值最小~

解法：这种题，一看题目让求的量基本上知道八成就是二分。这个题确实也是二分~二分那个最小值limit，然后求从顶点1到顶点n最少需要经过多少条边权大于limit的边。

花了20+分钟小水了一下~看会儿电视去~用G++47ms，900+k内存，C++交了一次32ms，400+k内存，竟然还排在rank 2。。。
View Code

#include <iostream>#include <cstdio>#include <cstring>#include <queue>usingnamespace std;constint N =1010;constint M =20100;int n, m, k, tot, dis[N], h[N], v[M], nxt[M], w[M];bool visit[N];queue <int> q;void add(int a, int b, int c){    v[tot] = b;    w[tot] = c;    nxt[tot] = h[a];    h[a] = tot++;}bool spfa(int limit){    int u, i, tmp;    while(!q.empty())  q.pop();    memset(visit, false, sizeof(visit));    memset(dis, -1, sizeof(dis));    q.push(1);    dis[1] =0;    while(!q.empty())    {        u = q.front();        q.pop();        visit[u] =false;        for(i = h[u]; i !=-1; i = nxt[i])        {            if(w[i] > limit)  tmp =1;            else  tmp =0;            if(dis[v[i]]==-1|| dis[v[i]]>dis[u]+tmp)            {                dis[v[i]] = dis[u] + tmp;                if(!visit[v[i]])                {                    visit[v[i]] =true;                    q.push(v[i]);                }            }        }        if(dis[n]!=-1&& dis[n]<=k)  returntrue;    }    returnfalse;}int main(){    int i, a, b, c, l, r, mid, ans;    scanf("%d%d%d", &n, &m, &k);    tot =0;    r =-1;    memset(h, -1, sizeof(h));    for(i =0; i < m; i++)    {        scanf("%d%d%d", &a, &b, &c);        add(a, b, c);        add(b, a, c);        r = max(r, c);    }    l =0;    ans =-1;    while(l <= r)    {        mid = (l+r) >>1;        if(spfa(mid))        {            ans = mid;            r = mid-1;        }        else  l = mid+1;    }    printf("%dn", ans);    return0;}

原文链接: https://www.cnblogs.com/zxndgv/archive/2011/08/15/2139151.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍