当前位置:网站首页>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
- Codeforces Global Round 19
- How to modify field constraints (type, default, null, etc.) in a table
- Failure causes and optimization methods of LTE CSFB
- Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
- Determine which week of the month the day is
- DM8 archive log file manual switching
- Oracle ORA error message
- Stc8h development (XII): I2C drive AT24C08, at24c32 series EEPROM storage
- 3分钟带你了解微信小程序开发
猜你喜欢
Benefits of automated testing
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
mysql从一个连续时间段的表中读取缺少数据
Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
How to standardize the deployment of automated testing?
Record the pit of NETCORE's memory surge
MySQL reads missing data from a table in a continuous period of time
【leetcode】1189. Maximum number of "balloons"
No qualifying bean of type ‘......‘ available
SSTI template injection explanation and real problem practice
随机推荐
80% of the diseases are caused by bad living habits. There are eight common bad habits, which are both physical and mental
The global and Chinese market of negative pressure wound therapy unit (npwtu) 2022-2028: Research Report on technology, participants, trends, market size and share
C#(三十)之C#comboBox ListView treeView
Facebook等大廠超十億用戶數據遭泄露,早該關注DID了
Ipv4中的A 、B、C类网络及子网掩码
How do we make money in agriculture, rural areas and farmers? 100% for reference
DM8 backup set deletion
Align items and align content in flex layout
Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
Factors affecting user perception
51nod 1130 n factorial length V2 (Stirling approximation)
[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
Solution to the problem that the root account of MySQL database cannot be logged in remotely
MySQL about self growth
判断当天是当月的第几周
pd. to_ numeric
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
How to execute an SQL statement in MySQL
asp. Core is compatible with both JWT authentication and cookies authentication
C#(二十七)之C#窗体应用