当前位置:网站首页>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;
}
边栏推荐
- Take you to wechat applet development in 3 minutes
- Stack and queue
- How to standardize the deployment of automated testing?
- Microkernel structure understanding
- Interface idempotency
- What is the difference between gateway address and IP address in tcp/ip protocol?
- C form application of C (27)
- MySql數據庫root賬戶無法遠程登陸解决辦法
- [matlab] - draw a five-star red flag
- 使用JS完成一个LRU缓存
猜你喜欢

Detailed explanation of serialization and deserialization

Record the pit of NETCORE's memory surge

Interface idempotency

在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
![[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)](/img/8a/068faf3e8de642c9e3c4118e6084aa.jpg)
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)

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

Thread sleep, thread sleep application scenarios
![[analysis of variance] single factor analysis and multi factor analysis](/img/92/5337d0ef6e487d1af2f56cb3a3268a.jpg)
[analysis of variance] single factor analysis and multi factor analysis

DM8 backup set deletion

mysql从一个连续时间段的表中读取缺少数据
随机推荐
Quick sort function in C language -- qsort
MySQL reads missing data from a table in a continuous period of time
Ipv4中的A 、B、C类网络及子网掩码
Chinese brand hybrid technology: there is no best technical route, only better products
Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
How can programmers resist the "three poisons" of "greed, anger and ignorance"?
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
Oracle ORA error message
Global and Chinese market of rubber wheel wedges 2022-2028: Research Report on technology, participants, trends, market size and share
Proof of Stirling formula
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
User datagram protocol UDP
Take you to wechat applet development in 3 minutes
Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
[meisai] meisai thesis reference template
[practical exercise] face location model based on skin color
自动化测试怎么规范部署?
Python book learning notes - Chapter 09 section 01 create and use classes