当前位置:网站首页>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;
}
边栏推荐
- Introduction to data types in MySQL
- Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
- Tips for using dm8huge table
- Viewing and verifying backup sets using dmrman
- 阿里测试师用UI自动化测试实现元素定位
- Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
- Failure causes and optimization methods of LTE CSFB
- Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
- /usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
- [prediction model] difference method model
猜你喜欢
![[Zhao Yuqiang] deploy kubernetes cluster with binary package](/img/45/6777fa919386e526dbb0d2c808a7f2.jpg)
[Zhao Yuqiang] deploy kubernetes cluster with binary package
![[Key shake elimination] development of key shake elimination module based on FPGA](/img/47/c3833c077ad89d4906e425ced945bb.png)
[Key shake elimination] development of key shake elimination module based on FPGA

MySql數據庫root賬戶無法遠程登陸解决辦法

Flask learning and project practice 9: WTF form verification
![Cf464e the classic problem [shortest path, chairman tree]](/img/6b/65b2dc62422a45cc72f287c38dbc58.jpg)
Cf464e the classic problem [shortest path, chairman tree]

cookie,session,Token 这些你都知道吗?

Align items and align content in flex layout

Redis (replicate dictionary server) cache
![[FPGA tutorial case 11] design and implementation of divider based on vivado core](/img/39/f337510c2647d365603a8485583a20.png)
[FPGA tutorial case 11] design and implementation of divider based on vivado core

The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
随机推荐
Record an excel xxE vulnerability
Take you to wechat applet development in 3 minutes
User experience index system
Record the pit of NETCORE's memory surge
Solution to the problem that the root account of MySQL database cannot be logged in remotely
Custom event of C (31)
Security xxE vulnerability recurrence (XXe Lab)
Simple blog system
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
Web components series (VII) -- life cycle of custom components
User datagram protocol UDP
Prime Protocol宣布在Moonbeam上的跨链互连应用程序
[FPGA tutorial case 11] design and implementation of divider based on vivado core
Maxay paper latex template description
51nod 1130 n factorial length V2 (Stirling approximation)
判断当天是当月的第几周
In Net 6 CS more concise method
math_极限&微分&导数&微商/对数函数的导函数推导(导数定义极限法)/指数函数求导公式推导(反函数求导法则/对数求导法)
Differential GPS RTK thousand search
pd. to_ numeric