Reward(拓扑排序)
http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:
老板要给n个员工发工资最低工资是888;
但是工人们是有要求的 如果输入 a b 表示a的工资要比b的工资高
求出老板最少准备多少工资
include
include
include
include
include
/**
1:拓扑排序(数据结构书上有)
用一个队列来储存入度为零的点
开始遍历这些点 遍历之后把以这个点开头的边删除比如a到b 遍历a时把b的度减一
2: 邻接表储存(用vector容器来实现邻接表的储存较为简单)
*/
using namespace std;
struct node
{
int b;
};
vectoredge[10005];
int du[10005];
int value[10005];
void creatLinJieBiao(int a,int b)///创建邻接表
{
node t;
t.b=b;
edge[a].push_back(t);///已a开头b结尾的边
du[b]++;///顶点b的入度加一
}
bool topSort(int n)///拓扑排序
{
queueq;
for(int i=1; i<=n; i++)
if(du[i]==0)q.push(i);
int count=0;
while(!q.empty())
{
int a=q.front();
count++;
q.pop();
for(int i=0; i<edge[a].size(); i++)
{
du[edge[a][i].b]--;
if(du[edge[a][i].b]==0)
{
value[edge[a][i].b]= value[a]+1;///b的只要比a的值高
q.push(edge[a][i].b);
}
}
}
if(count!=n)return false;///如果最后仍有某个点的度不为0那么即是存在环
return true;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(value,0,sizeof(value));
memset(du,0,sizeof(du));
memset(edge,0,sizeof(edge));
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
creatLinJieBiao(b,a);///要求a比b的值大
}
int sum=0;
if(topSort(n))
{
for(int i=1; i<=n; i++)
{
sum+=888+value[i];
}
printf("%d\n",sum);
}
else
printf("-1\n");
}
return 0;
}
/**
5 4
1 2
2 3
3 4
5 3
5 6
1 2
2 3
3 4
4 5
1 5
*/
最新文章
- 关于easyui datagrid 表格数据处理
- 关于px、em和rem的学习笔记!
- com.android.ide.common.process.ProcessException: org.gradle.process.internal.ExecException: Process &#39;command &#39; finished with non-zero exit value 1
- javascript实现原生ajax的方法
- BZOJ1452——[JSOI2009]Count
- ios 百度地图api 入门
- JVM性能调优
- 128. Longest Consecutive Sequence *HARD* -- 寻找无序数组中最长连续序列的长度
- 3des加解密算法
- java静态代理与动态代理简单分析
- 【EntityFramwork--处理数据并发问题】
- mysql 按月按周统计
- oracle linux下oracle 10g启动EM、isqlplus及相关命令语法
- (转) 各种好用的插件 Xcode
- JMXMP SSL
- 一步一步创建ASP.NET MVC5程序[Repository+Autofac+Automapper+SqlSugar](一)
- iOS在GitHub Top 前100 简介
- Redis的持久化之AOF方式
- JUnit的配置及使用
- [Linux] - 网速测试命令