首页 > ACM题库 > HDU-杭电 > HDU 3169-Balance-最短路径-[解题报告]HOJ
2014
03-06

HDU 3169-Balance-最短路径-[解题报告]HOJ

Balance

问题描述 :

A sailboat has many forces acting on it. This allows it to sail in many different directions, even if the wind is not blowing in the desired direction. In order for the boat to be easily controlled, however, certain forces must be balanced.

Suppose the wind is blowing from the north and the boat is facing west. Above the water, the blowing wind hits the sails, and because of the way that they are angled, pushes the boat to the southwest. The keel extends deep below the water. The water resistance on the keel creates a counterforce pushing the boat northward. Ideally, the northward force on the keel will counteract the southward component of the force on the sails, so that the boat will move to the west.

A problem can arise if the centre of the sails (called the Centre of Effort, or CE) is not directly above the centre of the keel (called the Centre of Lateral Resistance, or CLR). In general, the boat can pivot about the centre of the keel. If the sails are too far forward of the keel, the wind will push the bow (the front) of the boat southwards, and the boat will turn towards the south. If the sails are too far aft of (behind) the keel, the wind will push the stern (the back) southwards, and the boat will turn towards the north. Ideally, the sails and keel are balanced so that the boat sails in a straight line.

In this problem, you will examine a side view of the boat to determine whether the CE is above the CLR. The CE is defined as the centroid of the part of the boat above the waterline. The CLR is defined as the centroid of the part of the boat below the waterline. The centroid of a polygon is the unique point such that any line passing through it divides the polygon into two halves of equal area.

输入:

The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates.

输出:

The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates.

样例输入:

7
0 1
2 3
4 1
4 -3
2 -3
2 -1
0 -1

样例输出:

CE is aft of CLR by 0.50 units.

#include<iostream>
#include<queue>
using namespace std;
const int N = 1005;          //有N头牛
const int INF = 0x3f3f3f3f;  //定义一个大数作为无穷大
int NUM;                     //前向星变量,记录边数
int head[N];                 //前向星表头
bool flag[N];                //标记是否在队列
int dis[N];                  //标记1到其他顶点的最短距离
int sum[N];                  //标记入队次用,用于判断负环

struct Node{                 //记录关系
    int v,w,next;            //目标点,权值,下一点索引
}node[20005];


void add(int a,int b,int c){ //前向星加边函数
    node[NUM].v = b;
    node[NUM].w = c;
    node[NUM].next = head[a];
    head[a] = NUM++;
}

int SPFA(int s,int n){
    int i;
    for(i=0;i<=n;i++){    
        sum[i] = 0;         //初始化所有点入队次数为0
        flag[i] = false;    //初始化队列标记,false为未入队
        dis[i] = INF;       //初始化1到其他顶点距离为无穷大
    }
    queue<int> q;           //定义一个队列,存放维护的点
    q.push(s);              //把源点放进队列
    dis[s]=0;               //到自身距离为0
    while(!q.empty()){      //若队列不为空
        int u = q.front();  //取队列头元素
        q.pop();            //取元素后,元素弹出
        flag[u] = false;    //标记为不在队列
        for(i=head[u];~i;i=node[i].next)
        { //遍历与U相连的所有点
            int v = node[i].v;            //终点 
            int w = node[i].w;            //起点到终点权值
            if(dis[v] > dis[u] + w)
            {      //
                dis[v] = dis[u] + w;
                if(!flag[v])
                {             //若不再队列
                    q.push(v);            //把点放进队列维护 
                    flag[v] = true;       //标记为在队列
                    if(++sum[v] > n)
                    {     //入队数++,如果超过n,存在负环
                        return -1;  
                    }
                }
            }
        }

    }
    if(dis[n] == INF) return -2;
    return dis[n];
}

int main(){
    int n,ml,md,a,b,c;
    while(scanf("%d%d%d",&n,&ml,&md)!=EOF){
        memset(head,255,sizeof(head));   //初始化表头
        NUM = 0;
        while(ml--){                     //喜欢
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);                  //b-a<=c
        }
        while(md--){                     //不喜欢
            scanf("%d%d%d",&a,&b,&c); 
            add(b,a,-c);                 //b-a>=c
        }
        printf("%d\n",SPFA(1,n));
    }
    return 0;
}

参考:http://www.cnblogs.com/Deng1185246160/archive/2013/08/04/3235954.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。