转载

poj3660 Cow Contest（Floyd-Warshall方法求有向图的传递闭包）

poj3660

题意：

有n头牛，给你m对关系（a, b）表示牛a能打败牛b，求在给出的这些关系下，能确定多少牛的排名。

分析：

在这呢先说一下关系闭包：

关系闭包有三种：自反闭包（r），对称闭包（s），传递闭包（t)。

先画出 R 的关系图，再画出 r(R), s(R), t(R) 的关系图。

poj3660 Cow Contest（Floyd-Warshall方法求有向图的传递闭包）

我们今天用的是传递闭包。仅作为个人理解传递闭包：关系之间具有传递性（例如a> b, b> c, 那么a> c ），在那些已给出的关系基础上，通过传递性，把所有可能的关系都找出来。如上图。

这里需要先求一下所有牛之间的传递闭包，那么我们这题与传递闭包又有什么关系呢。下面将慢慢解答。

如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数x，和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了），再将满足这个条件的牛数目加起来就是所求解。 x可以看成是入度， y是出度。

在floyd-warshall（不了解该算法的点这里）求每对顶点间的最短路径算法中，可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-Wareshall。如果从 i 到 j 存在一条路径，则d(i,j)<N,否则d(i,j)=MAX。

一种改进的算法是：由于我们需要的只是判断是否从i到j存在一条通路，所以在Floyd-Wareshall中的动态规划比较中，我们可以把min和+操作改为逻辑or( || )和逻辑（&&）。也就是将 d[i][j] = min(d[i][j], d[i][k]+dist[k][j]); 改成 if(d [i][j] == 1 || (d[i][k] == 1 && d[k][j] == 1)) d[i][j] = 1;

设 d(i,j) ＝ 1表示从 i 到 j 存在一条通路 p，且 p 的所有中间节点都在0,1,2,...,k中, 否则d(i,j)=0。我们把边(i,j)加入到E*中当且仅当d(i,j)=1。

#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<vector> using namespace std; int n, m, ans, v[110][110]; void floyd()//求图的闭包， 把所有可以确定的关系都求出来 {  for(int k = 1; k <= n; k++)  {   for(int i = 1; i <= n; i++)   {    for(int j = 1; j <= n; j++)    {     if(v[i][j] == 1 || (v[i][k] == 1 && v[k][j] == 1))      v[i][j] = 1;    }   }  } } int main() {  while(scanf("%d%d", &n, &m) != EOF)  {   memset(v, 0, sizeof(v));   for(int i = 1; i <= m; i++)   {    int x, y;    scanf("%d%d", &x, &y);    v[x][y] = 1;   }   floyd();   ans = 0;   for(int i = 1; i <= n; i++)   {    int du = 0;    for(int j = 1; j <= n; j++)//对于每头牛， 求是否有唯一排名    {     if(i == j) continue;     if(v[i][j] == 1 || v[j][i] == 1)      du++;    }    if(du == n-1)     ans++;   }   printf("%d/n", ans);  }  return 0; }