注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1285  

2013-03-03 09:10:18|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1285
题意:有n个队伍比赛,m条比赛结果,即a赢b,求最后的排名。
题解:基础的拓扑排序。
第一次做拓扑排序的题,先整理下拓扑排序:
拓扑排序的定义:有n个变量,m个二元组(u,v),分别表示变量u小于v,求最后的排序结果。(当然这里二元组的关系可以有多种解释,有时候可以理解为先后顺序,即一个大任务分解成若干个小任务,必须先完成一些小任务后才能完成一个任务)
分析:
把每个变量看成一个点,二元组的关系看成有向边,这样就能得到一个有向图。这样,我们的任务实际上是把一个图的所有结点排序,使得每一个有向边(u,v)对应的u都排在v的前面。当然图中不可以出现环。
实现方法:
1、选择有向图中一个没有前驱的结点并输出,即该结点的入度为1
2、在有向图中删除该点,即删除该点出发的所有边
3、重复上述两步,直到输出所有点

/*
* test.cpp
*
* Created on: 2013-03-02
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 520
int n,g[N][N];

void fun()
{
int i,j,k,ru[N],vis[N],res[N];//res记录排序后的结果
memset(ru,0,sizeof(ru));//ru数组记录各个点的入度之和
memset(vis,0,sizeof(vis));//vis数组记录该点是否被访问
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(g[i][j]==1)
ru[j]++;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(!vis[j] && ru[j]==0)
{
res[i]=j;
vis[j]=1;
//更新,把从j出发的边去掉,即相应的入度减一
for(k=1;k<=n;k++)
if(g[j][k]==1)
ru[k]--;
break;
}
}
}
for(i=1;i<=n;i++)
{
if(i!=1)
printf(" ");
printf("%d",res[i]);
}
printf("\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(g,0,sizeof(g));
while(m--)
{
scanf("%d%d",&a,&b);
g[a][b]=1;
}
fun();
}
return 0;
}


  评论这张
 
阅读(90)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018