poj3249【拓扑排序】
2024-09-07 13:23:56
//题意: 给出一个有向无环图,每个顶点都有一个权值。
// 求一条从入度为0的顶点到出度为0的顶点的一条路径,
// 路径上所有顶点权值和最大。
// 求一条从入度为0的顶点到出度为0的顶点的一条路径,
// 路径上所有顶点权值和最大。
//我觉得只要明白
//图论里的链式前向星 的 建图原理 和 拓扑排序的一点知识就完全有能力打出来
//图论里的链式前向星 的 建图原理 和 拓扑排序的一点知识就完全有能力打出来
//以后还是可以练练手的 所以写一发吧
//拓扑排序+优化一下
//author keyboarder
//time 2016/4/23 21:52
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <queue>
#include <stack>
using namespace std;
#define INF 0x3f3f3f
#define pi acos(-1.0)
#define LL long long
#define mm 1000000007
//author keyboarder
//time 2016/4/23 21:52
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <queue>
#include <stack>
using namespace std;
#define INF 0x3f3f3f
#define pi acos(-1.0)
#define LL long long
#define mm 1000000007
#define N 1000010
struct asd{
int to;
int next;
};
asd q[N];
int head[N],tol;
int pre[N];
int out[N];
int val[N];
int dp[N];
int n,m;
int to;
int next;
};
asd q[N];
int head[N],tol;
int pre[N];
int out[N];
int val[N];
int dp[N];
int n,m;
void add(int a,int b)
{
q[tol].to=b;
q[tol].next=head[a];
head[a]=tol++;
}
{
q[tol].to=b;
q[tol].next=head[a];
head[a]=tol++;
}
void tuopu()
{
queue<int>e;
while(!e.empty())
e.pop();
for(int i=1;i<=n;i++)
{
if(pre[i]==0)
{
pre[i]=-1;
e.push(i);
}
}
while(!e.empty())
{
int u=e.front();
e.pop();
for(int v=head[u];v!=-1;v=q[v].next)
{
int i=q[v].to;
dp[i]=max(dp[u]+val[i],dp[i]);
pre[i]--;
if(pre[i]==0)
{
pre[i]=-1;
e.push(i);
}
}
}
}
{
queue<int>e;
while(!e.empty())
e.pop();
for(int i=1;i<=n;i++)
{
if(pre[i]==0)
{
pre[i]=-1;
e.push(i);
}
}
while(!e.empty())
{
int u=e.front();
e.pop();
for(int v=head[u];v!=-1;v=q[v].next)
{
int i=q[v].to;
dp[i]=max(dp[u]+val[i],dp[i]);
pre[i]--;
if(pre[i]==0)
{
pre[i]=-1;
e.push(i);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
}
int u,v;
tol=0;
memset(head,-1,sizeof(head));
memset(pre,0,sizeof(pre));
memset(out,0,sizeof(out));
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
pre[v]++;
out[u]++;
}
for(int i=1;i<=n;i++)
{
if(pre[i]==0)
{
dp[i]=val[i];
}
else
dp[i]=-INF;
}
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
}
int u,v;
tol=0;
memset(head,-1,sizeof(head));
memset(pre,0,sizeof(pre));
memset(out,0,sizeof(out));
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
pre[v]++;
out[u]++;
}
for(int i=1;i<=n;i++)
{
if(pre[i]==0)
{
dp[i]=val[i];
}
else
dp[i]=-INF;
}
tuopu();
int ans=-INF;
for(int i=1;i<=n;i++)
{
if(out[i]==0)
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
for(int i=1;i<=n;i++)
{
if(out[i]==0)
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- UNICODE
- HttpClient4.5 SSL访问工具类
- Python if条件语句
- (转载)Htmlparser Filter 简要归纳
- win8 mysqlzip install
- win7 IIS7.0 【IIS 管理器无法验证此内置帐户是否有访问权】
- Linux下套接字具体解释(三)----几种套接字I/O模型
- Machine Learning/Random Projection
- pip: unsupported locale setting
- Oracle-07:别名,去重,子查询
- 个人练习:使用HTML+CSS3制作图片轮播功能(不使用JavaScript)
- 从零开始搭建自己的VueJS2.0+ElementUI单页面网站(一、环境搭建)
- 你不知道的react
- vector的多套遍历方案
- 客户端服务端web问题
- Docker技术入门与实战 第二版-学习笔记-10-Docker Machine 项目-2-driver
- quantum theory
- EF学习笔记-1 EF增删改查
- php集群和分布式理解
- mysql-5.6.22的安装步骤
热门文章
- 使用Python控制1602液晶屏实时显示时间(附PyCharm远程调试)
- HDU 3118 Arbiter 判定奇圈
- react 使用 moment 进行 日期格式化
- react jsx 数组变量的写法
- Ikki&;#39;s Story IV - Panda&;#39;s Trick (poj 3207 2-SAT)
- C++经典面试题解析
- 从Nginx源代码谈大写和小写字符转化的最高效代码以及ASCII码表的科学
- Intel Chipsets
- 用JAVA编写浏览器内核之实现javascript的document对象与内置方法
- IconTabPageIndicator