POJ 3660 Cow Contest(最短路弗洛伊德预处理或者迪杰斯克拉)

5 5
4 3
4 2
3 2
1 2
2 5

2

思路：用迪杰斯克拉枚举每一头牛（假设是i）看这头牛跟其他n-1头牛（假设是j）是否可以确定关系，如果不能再迪杰斯克拉这头不能的j牛，看j到i能不能确定关系，如果还不能那这头牛（i牛）就不能确定等级了。这样既竟然没有超时，不过时间复杂度确实挺高的。

做完以后搜博客发现可以用弗洛伊德预处理出每两头牛之间是否可以分出胜负，然后只需判断每头牛跟其他n-1头牛之间是否可以确定关系即可。

迪杰斯克拉：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3fffffff
const int N=100;
int e[N+5][N+5],dis1[N+5],dis2[N+5],n,m;
bool vis[N+5];
void dijkstra(int dis[],int x)
{
memset(vis,false,sizeof(vis));
for(int i=0;i<n;i++)
dis[i]=e[x][i];
for(int i=0;i<n-1;i++)
{
int u=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis[j])//这里不存在找最大最小值了，所以只要dis[j]有值就取，并且取到了就跳出
{
u=j;
break;
}
}
if(u==-1) return ;
vis[u]=true;
for(int j=0;j<n;j++)
if(!vis[j]&&!dis[j]&&e[u][j])//判断x与j是否存在关系，如果不存在并且u与j有关系那么x与j的关系就能确定，因为关系是单方向的
dis[j]=1;//x与j有关系，赋值为1
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
scanf("%d%d",&n,&m);
int a,b,flag,ans=0;
memset(e,0,sizeof(e));
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
e[a-1][b-1]=1;//a到b（不是b到a，有向图）有关系，赋值为1
}
for(int i=0;i<n;i++)//遍历每一个点，看这个点与其他n-1个点是否都有关系
{
flag=1;
dijkstra(dis1,i);
for(int j=0;j<n;j++)
{
if(i==j) continue;
if(!dis1[j])//如果i到j没有关系，那么就看j到i有没有关系，因为两头牛之间只有有一条单向路就可以了
{
dijkstra(dis2,j);
if(!dis2[i])
{
flag=0;
break;
}
}
}
if(flag)//该头牛与其他n-1头牛都能确定关系，那么这头牛的等级就能确定
ans++;
}
printf("%dn",ans);
}
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3fffffff
const int N=100;
int e[N+5][N+5],m,n;
void floyd()
{
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!e[i][j]&&e[i][k]&&e[k][j])//找关系
e[i][j]=1;
}
int main()
{
int a,b;
while(~scanf("%d%d",&n,&m))
{
memset(e,0,sizeof(e));
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
e[a-1][b-1]=1;
}
floyd();
int ans=0,flag;
for(int i=0;i<n;i++)
{
flag=1;
for(int j=0;j<n;j++)
{
if(i==j) continue;
if(!e[i][j]&&!e[j][i])//如i到j和j到i都没有关系，那么i的登记就不能确定了
{
flag=0;
break;
}
}
if(flag) ans++;
}
printf("%dn",ans);
}
}

最后

以上就是阔达项链为你收集整理的POJ 3660 Cow Contest(最短路弗洛伊德预处理或者迪杰斯克拉)的全部内容，希望文章能够帮你解决POJ 3660 Cow Contest(最短路弗洛伊德预处理或者迪杰斯克拉)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。