【洛谷P1073】[NOIP2009]最优贸易
2024-09-02 08:13:22
最优贸易
看题解后感觉分层图好像非常NB巧妙
建三层n个点的图,每层图对应的边相连,权值为0
即从一个城市到另一个城市,不进行交易的收益为0
第一层的点连向第二层对应的点的边权为-w[i],表示买入的收益
第二层的点连向第三层对应的点的边权为w[i],表示卖出的收益
这样跑一遍最长路,就可以了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 300030
#define M 1200030
int n,m,dis[N],tot,Head[N];
queue<int> q;
bool inque[N];
struct NODE{
int to,next,w;
} e[M];
inline int read(){
int x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
inline void add(int x,int y,int w){
e[++tot].to=y;
e[tot].w=w;
e[tot].next=Head[x];
Head[x]=tot;
}
inline void unionn(int x,int y){
add(x,y,);
add(x+n,y+n,);
add(x+n+n,y+n+n,);
}
int main()
{
n=read(); m=read();
int x,y,z;
for(int i=;i<=n;i++){
x=read();
add(i,i+n,-x);
add(i+n,i+n+n,x);
}
add(n,n+n+n+,);
for(int i=;i<=m;i++){
x=read(); y=read(); z=read();
unionn(x,y);
if(z==) unionn(y,x);
}
add(n+n+n,n+n+n+,);
memset(dis,-,sizeof(dis));
q.push(); dis[]=;
while(!q.empty()){
int u=q.front(); q.pop();
inque[u]=;
for(int i=Head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!inque[v]){
inque[v]=;
q.push(v);
}
}
}
}
printf("%d\n",dis[n+n+n+]);
return ;
}
最新文章
- 【转】PowerShell 函数(Function)
- ubuntu 安装redis两种方式 教程
- javascript位运算
- cocos2dx lua中继承与覆盖C++方法
- js快速排序法
- mycat(4)
- linux之SQL语句简明教程---INSERT INTO
- poj 1159 Palindrome(区间dp)
- WebService 通过POST方式访问时候,因 URL 意外地以“/方法名”结束,请求格式无法识别 解决办法
- Beautifulsoup 和selenium 的查询
- 四、I/O
- 使用Spring MVC构建REST风格WEB应用
- C# 跳转新的标签页
- mysql数据库建表的基本规范
- java jdbc ResultSet结果通过java反射赋值给java对象
- cmd中运行maven -v提示JAVA_HOME的配置问题解决办法
- 基于MMSE的预测
- vs2015转到定义没反应
- python中高阶函数与装饰器
- 使用TensorFlow低级别的API进行编程