POJ - 3660 Cow Contest 特殊的最短路

本文主要是介绍POJ - 3660 Cow Contest 特殊的最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-3660

题意

给定n个节点，给出m个节点大小关系，求能确定多少个节点的排名

解法

如果要确定排名，那么比这个节点大的节点和比这个节点小的节点的数量应该是确定的。我们将这种大小关系转换为图，对于A>B，我们从节点B向节点A连接一条单向边（A向B链接也是可以的）。那么对于任意节点K，K所能到达的节点都是比它大的，所有可以到达K的节点都是比他小的。那么计算这两个数字，如果相加等于n-1，那么K的排位就是唯一确定的了。
因为n范围很小，直接选择邻接矩阵+floyd，将初始dis设为inf，那么跑完后遍历，dis不为inf的就是可以到达。两次遍历就可以了。

代码

#include<iostream>
#include<cstring>  
#include<queue>
#include<string>
#include<algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;typedef pair <int,int> P;const int maxn=105;const int inf=0x3f3f3f3f;int n,m;int graph[maxn][maxn],_in[maxn],_out[maxn];int main(){IOSmemset(graph,0x3f,sizeof(graph));cin>>n>>m;while(m--){int u,v;cin>>u>>v;graph[v][u]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(graph[i][j]>graph[i][k]+graph[k][j])graph[i][j]=graph[i][k]+graph[k][j];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(graph[i][j]!=inf)_out[i]++;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(graph[i][j]!=inf)_in[j]++;}}int ans=0;for(int i=1;i<=n;i++){if(_in[i]+_out[i]==n-1)ans++;}cout<<ans<<endl;}