当前位置:网站首页>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;
}
边栏推荐
- 自动化测试怎么规范部署?
- Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
- Mathematical modeling regression analysis relationship between variables
- 【按鍵消抖】基於FPGA的按鍵消抖模塊開發
- STC8H开发(十二): I2C驱动AT24C08,AT24C32系列EEPROM存储
- Conditionally [jsonignore]
- Interface idempotency
- How can programmers resist the "three poisons" of "greed, anger and ignorance"?
- Serial port-rs232-rs485-ttl
- ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
猜你喜欢
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
Fundamentals of SQL database operation
综合能力测评系统
[Massey] Massey font format and typesetting requirements
记一次excel XXE漏洞
Blue Bridge Cup - Castle formula
User experience index system
How does technology have the ability to solve problems perfectly
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
Cf464e the classic problem [shortest path, chairman tree]
随机推荐
C#(三十一)之自定义事件
【FPGA教程案例11】基于vivado核的除法器设计与实现
Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
记一次excel XXE漏洞
Why do you want to start pointer compression?
[practice] mathematics in lottery
User experience index system
Codeforces Round #770 (Div. 2) B. Fortune Telling
Do you know cookies, sessions, tokens?
C language -- structs, unions, enumerations, and custom types
Mathematical modeling regression analysis relationship between variables
KS008基于SSM的新闻发布系统
MySql數據庫root賬戶無法遠程登陸解决辦法
mysql关于自增长增长问题
How does technology have the ability to solve problems perfectly
Microkernel structure understanding
Facebook等大厂超十亿用户数据遭泄露,早该关注DID了
Maxay paper latex template description
math_ Derivative function derivation of limit & differential & derivative & derivative / logarithmic function (derivative definition limit method) / derivative formula derivation of exponential functi
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)