首页 > ACM题库 > HDU-杭电 > HDU 3772-Tunnelling the Earth-字符串-[解题报告]HOJ
2015
04-10

HDU 3772-Tunnelling the Earth-字符串-[解题报告]HOJ

Tunnelling the Earth

问题描述 :

There are different methods of transporting people from place to place: cars, bikes, boats, trains, planes, etc. For very long distances, people generally fly in a plane. But this has the disadvantage that the plane must fly around the curved surface of the earth. A distance travelled would be shorter if the traveller followed a straight line from one point to the other through a tunnel through the earth.

For example, travelling from Waterloo to Cairo requires a distance of 9293521 metres following the great circle route around the earth, but only 8491188 metres following the straight line through the earth.

For this problem, assume that the earth is a perfect sphere with radius of 6371009 metres.

输入:

The first line of input contains a single integer, the number of test cases to follow. Each test case is one line containing four floating point numbers: the latitude and longitude of the origin of the trip, followed by the latitude and longitude of the destination of the trip. All of these measurements are in degrees. Positive numbers indicate North latitude and East longitude, while negative numbers indicate South latitude and West longitude.

输出:

The first line of input contains a single integer, the number of test cases to follow. Each test case is one line containing four floating point numbers: the latitude and longitude of the origin of the trip, followed by the latitude and longitude of the destination of the trip. All of these measurements are in degrees. Positive numbers indicate North latitude and East longitude, while negative numbers indicate South latitude and West longitude.

样例输入:

1
43.466667 -80.516667 30.058056 31.228889

样例输出:

802333

HDU_3772

    我们可以把一个字符串拆成两个点分别代表入度和出度,然后用KM算法去做二分图最优匹配即可。

#include<stdio.h>
#include<string.h>
#define MAXD 210
#define INF 1000000000
char b[MAXD][1010];
int G[MAXD][MAXD] , yM[MAXD], N;
int A[MAXD], B[MAXD], slack;
int visx[MAXD], visy[MAXD];
int check(char *str1, char *str2)
{
    int i, j, num = 0;
    i =strlen(str1) - 1;
    for(j = 0; str1[i] == str2[j] && i >= 0 && str2[j]; i --, j ++)
        num ++;
    return num;
}
void init()
{
    int i, j, k;
    for(i = 0; i < N; i ++)
        scanf("%s", b[i]);
    memset(G, 0, sizeof(G));
    for(i = 0; i < N; i ++)
        for(j = i + 1; j < N; j ++)
        {
            G[i][j] = check(b[i], b[j]);
            G[j][i] = check(b[j], b[i]);
        }
}
int searchpath(int u)
{
    int v, temp;
    visx[u] = 1;
    for(v = 0; v < N; v ++)
        if(!visy[v])
        {
            temp = A[u] + B[v] - G[u][v];
            if(temp == 0)
            {
                visy[v] = 1;
                if(yM[v] == -1 || searchpath(yM[v]))
                {
                    yM[v] = u;
                    return 1;
                }
            }
            else if(temp < slack)
                slack = temp;
        }
    return 0;
}
void KM()
{
    int i, j, u;
    for(i = 0; i < N; i ++)
    {
        A[i] = 0;
        for(j = 0; j < N; j ++)
            if(G[i][j] > A[i])
                A[i] = G[i][j];
    }
    memset(B, 0, sizeof(B));
    memset(yM, -1, sizeof(yM));
    for(u = 0; u < N; u ++)
        for(;;)
        {
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            slack = INF;
            if(searchpath(u))
                break;
            for(i = 0; i < N; i ++)
            {
                if(visx[i])
                    A[i] -= slack;
                if(visy[i])
                    B[i] += slack;
            }
        }
}
void printresult()
{
    int i, res = 0;
    for(i = 0; i < N ; i ++)
        res += G[yM[i]][i];
    printf("%d\n", res);
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        KM();
        printresult();
    }
    return 0;
}


参考:http://www.cnblogs.com/staginner/archive/2011/10/05/2199449.html


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept