当前位置:网站首页>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;
}
边栏推荐
- DM8 backup set deletion
- C#(二十八)之C#鼠标事件、键盘事件
- Global and Chinese markets for patent hole oval devices 2022-2028: Research Report on technology, participants, trends, market size and share
- 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
- Record an excel xxE vulnerability
- 80% of the diseases are caused by bad living habits. There are eight common bad habits, which are both physical and mental
- WPF effect Article 191 box selection listbox
- Factors affecting user perception
- Redis (replicate dictionary server) cache
- [disassembly] a visual air fryer. By the way, analyze the internal circuit
猜你喜欢

Thread sleep, thread sleep application scenarios

math_ Derivative function derivation of limit & differential & derivative & derivative / logarithmic function (derivative definition limit method) / derivative formula derivation of exponential functi
![[Massey] Massey font format and typesetting requirements](/img/27/6b641551d6d8699683972f40f3b8e5.jpg)
[Massey] Massey font format and typesetting requirements

Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did

C#(二十九)之C#listBox checkedlistbox imagelist

在 .NET 6 中使用 Startup.cs 更简洁的方法

Database, relational database and NoSQL non relational database

SSTI template injection explanation and real problem practice

Record the pit of NETCORE's memory surge

No qualifying bean of type ‘......‘ available
随机推荐
Hashcode and equals
在 .NET 6 中使用 Startup.cs 更简洁的方法
Microkernel structure understanding
记一次excel XXE漏洞
How do we make money in agriculture, rural areas and farmers? 100% for reference
C mouse event and keyboard event of C (XXVIII)
[meisai] meisai thesis reference template
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
Oracle ORA error message
Maxay paper latex template description
Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
[American competition] mathematical terms
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
Record the pit of NETCORE's memory surge
MySQL about self growth
Viewing and verifying backup sets using dmrman
Simple blog system
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Class A, B, C networks and subnet masks in IPv4
An article will give you a comprehensive understanding of the internal and external components of "computer"