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 ;
}