首页 > 代码库 > 确定比赛名次

确定比赛名次

2024-07-10 00:57:39   223人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1285

拓扑排序：次序问题

AOV网：

用顶点表示活动，弧表示活动间的优先关系的有向图，AOV网中不应该出现有向环：
如果存在环，则某项活动以自己为先决条件。
 
 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 int n,m; 5 int map[501][501],d[501],v[501]; 6 int main() 7 { 8     int x,y; 9     int flag;10     while(scanf("%d%d",&n,&m)!=EOF)11     {12         memset(v,0,sizeof(v));13         memset(d,0,sizeof(d));14         memset(map,0,sizeof(map));15         while(m--)16         {17             scanf("%d%d",&x,&y);18             if(!map[x][y])19             {20                 map[x][y]=1;21                 d[y]++;22             }23         }24         flag=0;25         for(int i=1;i<=n;i++)26         {27             for(int j=1;j<=n;j++)28             {29                 if(v[j]==0&&d[j]==0)30                 {31                     for(int k=1;k<=n;k++)32                         if(map[j][k])33                           d[k]--;34                     v[j]=1;35                     if(flag==0)36                     {37                          printf("%d",j);38                          flag=1;39                     }40                     else printf(" %d",j);41                     break;42                 }43             }44         }45         printf("\n");46 47     }48     return 0;49 }

 


联系
我们