P1938 [USACO09NOV]找工就业Job Hunt

题目传送门

解析：

题目释义：一张图有c个节点，每个节点有一个相等的权值d，有p条无需花费的路径和f条需要花费的路径，求图中最长路。

算法设计：

由于可能出现正环，所以需要SPFA算法，在加边的时候把p条无需花费的路径边权设为d，而f条需要花费的路径设为d-z（其中z是这条路需要的花费）。由于终点不定，所以最后打擂台取最大值即可。

算法步骤：

1）读入，邻接表存边，存法上文已经提到

2）跑SPFA求最长路+判正环，如果有正环就可以无限走，输出-1直接退出

3）打擂台取最大值输出即可

参考程序如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<algorithm>
 7 using namespace std;
 8 int d,p,c,f,s,x,y,z,v[100001],w[100001],head[100001],nxt[100001],r[100001],cnt,maxx,dist[100001]; 
 9 bool vis[100001];
10 void add(int a,int b,int c)
11 {
12     v[++cnt]=b;
13     w[cnt]=c;
14     nxt[cnt]=head[a];
15     head[a]=cnt;
16 }
17 void read()
18 {
19     cin>>d>>p>>c>>f>>s;
20     for(int i=1;i<=p;i++)
21     {
22         cin>>x>>y;
23         add(x,y,d);
24     }
25     for(int i=1;i<=f;i++)
26     {
27         cin>>x>>y>>z;
28         add(x,y,d-z);
29     }
30 }
31 void pr()
32 {
33     for(int i=1;i<=c;i++)
34     {
35         maxx=max(maxx,dist[i]);
36     } 
37     cout<<maxx;
38 }
39 void spfa(int s)
40 {
41     memset(dist,-1,sizeof(dist));
42     queue<int>q;
43     q.push(s);
44     vis[s]=1;
45     dist[s]=d;
46     while(!q.empty())
47     {
48         int t=q.front();
49         q.pop();
50         vis[t]=0;
51         r[t]++;
52         if(r[t]==c)
53         {
54             cout<<"-1";
55             exit(0);
56         }
57         for(int i=head[t];i;i=nxt[i])
58         {
59             int y=v[i];
60             if(dist[y]<dist[t]+w[i])
61             {
62                 dist[y]=dist[t]+w[i];
63                 if(!vis[y])
64                 {
65                     q.push(y);
66                     vis[y]=1;
67                 }
68             }
69         }
70     }
71 }
72 int main()
73 {
74     read();
75     spfa(s);
76     pr();
77     return 0;
78 }

View Code

P1938 [USACO09NOV]找工就业Job Hunt

相关推荐