河北省建设工程协会网站,对钩网机械加工订单,seo的概念,网站关键字优化价格今天去听2015ZJOI浙江省队第二试的集训#xff0c;早上就是听得云里雾里的ORZ#xff0c;下午某两集训队大神过来将题目#xff0c;第一个进了IOI的我只听懂了10%ORZ#xff0c;第二个人机交互很好玩#xff0c;找个时间单独写下。 顺便附带膜拜各位聚聚#xff0c;保我明… 今天去听2015ZJOI浙江省队第二试的集训早上就是听得云里雾里的ORZ下午某两集训队大神过来将题目第一个进了IOI的我只听懂了10%ORZ第二个人机交互很好玩找个时间单独写下。 顺便附带膜拜各位聚聚保我明天ZJOI不爆0........ ORZZLD ORZYSY ORZWYH ORZCJH ORZZZQ 好了切入正题—— 华丽的分割线 今天我们来打打SPFA模板。 去年NOIP我SPFA之前突击了下然后day2果然我就用spfa坑了T2 60分简直了然而T1写跪了其实没啥区别。然后我就发现SPFA挺重要的这几天重新捡起来看看。 先发上代码再说 1 #includebits/stdc.h2 using namespace std;3 const int MAX10000;4 struct node {5 int to,w,next;6 }edge[MAX];7 bool used[MAX];8 int outqueue[MAX],head[MAX],low[MAX],n,m;9 bool spfa(int start) {
10 queueint q;
11 used[start]1;
12 low[start]0;
13 q.push(start);
14 while(!q.empty()) {
15 int topq.front();
16 q.pop();used[top]0;
17 outqueue[top];
18 if(outqueue[top]n) return 0;
19 for (int khead[top];k!-1;kedge[k].next)
20 if(low[edge[k].to]low[top]edge[k].w) {
21 low[edge[k].to]low[top]edge[k].w;
22 if(!used[edge[k].to]) {
23 used[edge[k].to]1;
24 q.push(edge[k].to);
25 }
26 }
27 }
28 return 1;
29 }
30 int main() {
31 memset(used,0,sizeof(used));
32 memset(head,-1,sizeof(head));
33 memset(outqueue,0,sizeof(outqueue));
34 memset(low,2100000,sizeof(low));
35 scanf(%d%d,n,m);
36 for (int i1,k0; im; i) {
37 int from,to,wei;
38 scanf(%d%d%d,from,to,wei);
39 edge[k].toto;
40 edge[k].wwei;
41 edge[k].nexthead[from];
42 head[from]k;
43 }
44 if(spfa(1)) printf(%d\n,low[n]);
45 else printf(存在负权环\n);
46 return 0;
47 } View Code P.S:2015/5/22修改原来的那份网络上的模板用完并没有将used清零导致了一些小错误。 今天在动车高铁上好好理解了下SPFA弄明白了 next数组存的是和当前边一个起点的下/上一条边。 head[i]存的是以i为起点有多少条边。 w就不用讲了边的权值。 SPFA的复杂度为O(kE)k是常数所以经常被fzyz的orz神牛们使用。 其实SPFA也不难就那样有点小坑 我是开了个结构体个人不太喜欢(习惯)写指针以前写指针跪了好多果然指针没学好。。。 我都不用指针的除非万不得已然而万不得已没有出现过。 ——wyh大聚聚 我都喜欢用指针因为“-”看起来很有美感。。 ——cjh大聚聚 好吧话题跑歪了下面列出可以参考的列表 http://blog.csdn.net/chenjiang492943457/article/details/5375413 http://www.cnblogs.com/devtang/archive/2011/08/25/spfa.html http://baike.baidu.com/link?urlO0QvxbOY8SVBjrIl6nF6EvMHSslgcEIxfXSoty5SbkA7QjbWZjTWARzwTQsKKbSD5mlASljndZrqYjle_qwcmq 然而我发现SPFA还有优化 LLL和SLF改天去看看然后再写个模板 最后声明下我并不是ZJ的 |||转载于:https://www.cnblogs.com/TonyNeal/p/SPFAtem.html
