当前位置:网站首页>P2648 make money
P2648 make money
2022-07-06 04:03:00 【Zhong Zhongzhong】
https://www.luogu.com.cn/problem/P2648
This question is great , I always thought that the toxic tumor data would not let me pass , It's actually my own low-level mistake .
General train of thought : Find the longest path , But because the starting point is uncertain , We need to introduce a super source , The distance from this source point to any point is 0.
Another key point of this topic is : The weight of the point is converted to the edge , I believe everyone will ; however , We all know that this introduced super source is not profitable , But in the code, the value assigned to him is d, Because the city at the other end of our connection is by weight d Of , But we assign the edge 0, So we need to put the other end of the city d Move to the source .
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e5+5;
int head[maxn],d,p,c,f,s,cnt,pp[maxn],dis[maxn];
bool vis[maxn],flag;
struct node
{
int to,dis,nxt;
}e[maxn];
void add_edge(int from,int to,int w)
{
e[++cnt].to=to;
e[cnt].dis=w;
e[cnt].nxt=head[from];
head[from]=cnt;
}
queue<int>q;
void spfa()
{
dis[s]=d;
q.push(s);
vis[s]=1;
pp[s]++;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
if(++pp[u]>c)
{
printf("orz\n");
flag=1;
return;
}
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]<dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&d,&p,&c,&f);
s=c+1;c=c+1;
head[0]=-1;
for(int i=1;i<=c;i++)
head[i]=-1,dis[i]=-inf;
for(int i=1;i<=p;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,d);
}
for(int i=1;i<=f;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,d-w);
}
for(int i=1;i<=c;i++)
add_edge(s,i,0);
spfa();
if(flag)
return 0;
int tmp=0;
for(int i=1;i<=c;i++)
{
tmp=max(tmp,dis[i]);
}
cout<<tmp<<endl;
return 0;
}
边栏推荐
- C form application of C (27)
- Oracle ORA error message
- Benefits of automated testing
- [FPGA tutorial case 12] design and implementation of complex multiplier based on vivado core
- Exchange bottles (graph theory + thinking)
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
- TCP/IP协议里面的网关地址和ip地址有什么区别?
- LTE CSFB test analysis
- Solution to the problem that the root account of MySQL database cannot be logged in remotely
- Global and Chinese markets for patent hole oval devices 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
Cf464e the classic problem [shortest path, chairman tree]
[PSO] Based on PSO particle swarm optimization, matlab simulation of the calculation of the lowest transportation cost of goods at material points, including transportation costs, agent conversion cos
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
TCP/IP协议里面的网关地址和ip地址有什么区别?
MySql數據庫root賬戶無法遠程登陸解决辦法
DM8 backup set deletion
How to standardize the deployment of automated testing?
Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)
How do we make money in agriculture, rural areas and farmers? 100% for reference
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
随机推荐
[Massey] Massey font format and typesetting requirements
潘多拉 IOT 开发板学习(HAL 库)—— 实验9 PWM输出实验(学习笔记)
WPF effect Article 191 box selection listbox
Hashcode and equals
Do you know cookies, sessions, tokens?
Global and Chinese market of rubber wheel wedges 2022-2028: Research Report on technology, participants, trends, market size and share
Record the pit of NETCORE's memory surge
Oracle ORA error message
Factors affecting user perception
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
[adjustable delay network] development of FPGA based adjustable delay network system Verilog
Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
自动化测试怎么规范部署?
[optimization model] Monte Carlo method of optimization calculation
如何修改表中的字段约束条件(类型,default, null等)
Maxay paper latex template description
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
[Key shake elimination] development of key shake elimination module based on FPGA
Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
Detailed explanation of serialization and deserialization