POJ 2253 Frogger ，poj3660Cow Contest（判断绝对顺序）（最短路，floyed）

POJ 2253 Frogger题目意思就是求所有路径中最大路径中的最小值。

#include<iostream>

#include<cstdio>

#include<string.h>

#include <utility>//make_pair的头文件

#include<math.h>

using namespace std;

const int maxn=;

double map[maxn][maxn];

int n;

typedef struct pair<int,int> PAIR_IF;

double max(int a,int b)

{

    if(a>b)

    return a;

    else

    return b;

}

void floyd()

{

    for(int v=;v<=n;v++)

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(map[i][j]>max(map[i][v],map[v][j]))

    map[i][j]=max(map[i][v],map[v][j]);

    printf("Frog Distance = %.3f\n\n",map[][]);

}

double dis(PAIR_IF p1,PAIR_IF p2)

{

    return (sqrt((double)(p1.first-p2.first)*(p1.first-p2.first)+(p2.second-p1.second)*(p2.second-p1.second)));

}

int main()

{

    std::ios::sync_with_stdio(false);//用这个语句，取消cin，cout与stdio的同步，就是提速，效率基本与scanf和printf一致。

    int a,b;

    PAIR_IF p[maxn];

    int t=;

    while(cin>>n&&n!=)

    {

        for(int i=;i<=n;i++)

        {

            cin>>a>>b;

            p[i]=make_pair(a,b);

        }

        for(int i=;i<=n;i++)

        {

            for(int j=i;j<=n;j++)

            {

            if(i==j)

            map[i][j]=;

            map[j][i]=map[i][j]=dis(p[i],p[j]);

            }

        }

        cout<<"Scenario #"<<t<<endl;

        floyd();

        t++;

    }

    return ;

}

poj3660Cow Contest（判断绝对顺序）题目意思是给出牛的数量n和牛之间的胜负关系m，让你求出可确定排名的牛的数量

列如：输入:

5 5（5头牛  5关系）
4 3（牛4可打败牛3）

4 2（牛4可打败牛2）
3 2（牛3可打败牛2）
1 2（牛1可打败牛2）
2 5（牛2可打败牛5）

输出：2（牛1和牛5可确定排名）

代码：

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

using namespace std;

const int MAXN=;

int win[MAXN][MAXN];

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(win,,sizeof(win));

        int u,v;

        while(m--)//m种关系

        {

            scanf("%d%d",&u,&v);

            win[u][v]=;  //u可以直接打败v

        }

        for(int k=;k<=n;k++)  //i间接打败j

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                    if(win[i][k]&&win[k][j])

                        win[i][j]=;

        int ans=;//记录有几头牛可以确定排名

        int j;

        for(int i=;i<=n;i++)

        {

            for(j=;j<=n;j++)//与所有牛都有关系就能够确定绝对顺序

            {

                if(i==j)

                continue;

                if(win[i][j]==&&win[j][i]==)

                break;//关系不确定

            }

            if(j>n)

            ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}