蓝书3.3 SPFA算法的优化

T1 最小圈 bzoj 1486

题目大意：

一个环的权值平均值为定义为一个这个环上所有边的权值和除以边数

求最小的环的权值平均值

思路：

二分一个值把所有边减去这个值

判断是否有负环

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 1061109567
10 #define ll long long
11 #define MAXN 6010
12 #define eps 1e-9
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,m,vis[MAXN],fa[MAXN],q[MAXN],f;
22 double l,r,mid,ans,dis[MAXN],val[MAXN<<1],v[MAXN<<1];
23 int to[MAXN<<1],nxt[MAXN<<1],fst[MAXN],cnt;
24 void add(int u,int v,double w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
25 void spfa(int x)
26 {
27     vis[x]=1;
28     for(int i=fst[x];i;i=nxt[i])
29         if(dis[x]+v[i]<dis[to[i]])
30             if(vis[to[i]]){f=1;return;}
31             else {dis[to[i]]=v[i]+dis[x];spfa(to[i]);}
32     vis[x]=0;
33 }
34 int check(double x)
35 {
36     for(int i=1;i<=cnt;i++) v[i]=val[i]-x;
37     for(int i=1;i<=n;i++) dis[i]=0.0;
38     memset(vis,0,sizeof(vis));f=0;
39     for(int i=1;i<=n;i++)
40         {spfa(i);if(f) return 1;}
41     return 0;
42 }
43 int main()
44 {
45     n=read(),m=read();int a,b;double c;
46     while(m--) {a=read(),b=read();scanf("%lf",&c);add(a,b,c);}
47     l=-1e7,r=1e7;
48     while(r-l>=eps)
49     {
50         mid=(l+r)/2.0;
51         if(check(mid)) ans=mid,r=mid-eps;
52         else l=mid+eps;
53     }
54     printf("%.8lf",ans);
55 }

View Code

T2 虫洞 bzoj 1715

题目大意：

一个无向图中有一些虫洞虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻

求是否可以借助这些虫洞来回到出发时刻之前

思路：

把有向图的边权改为负的直接用dfs的spfa判负环即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 1061109567
10 #define ll long long
11 #define MAXN 3010
12 #define eps 1e-5
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,m1,m2,dis[MAXN],vis[MAXN],fa[MAXN],q[MAXN],f;
22 int to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],fst[MAXN],cnt;
23 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
24 void spfa(int x)
25 {
26     vis[x]=1;
27     for(int i=fst[x];i;i=nxt[i])
28         if(dis[x]+val[i]<dis[to[i]])
29             if(vis[to[i]]){f=1;return;}
30             else {dis[to[i]]=val[i]+dis[x];spfa(to[i]);}
31     vis[x]=0;
32 }
33 int main()
34 {
35     int T=read();
36     while(T--)
37     {
38         n=read(),m1=read(),m2=read(),f=0;int a,b,c;
39         memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));
40         memset(fst,0,sizeof(fst));cnt=0;
41         while(m1--) {a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);}
42         while(m2--) {a=read(),b=read(),c=read();add(a,b,-c);}
43         for(int i=1;i<=n;i++)
44             {spfa(i);if(f) {puts("YES");goto ed;}}
45         puts("NO");
46         ed:;
47     }
48 }

View Code

T3 Easy sssp vijos 1053

题目大意：

判断这个有向图中是否存在负权回路

如果存在负权回路, 只输出一行-1 如果不存在负权回路, 再求出一个点S到每个点的最短路的长度

思路：

不知道我的dfs spfa 为什么T了

于是选择bfs 如果一个点进队n次则有负环

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2147483647
10 #define ll long long
11 #define MAXN 50100
12 #define eps 1e-9
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,m,vis[MAXN],fa[MAXN],q[MAXN<<5],l,r,f,st,inq[MAXN],num[MAXN];
22 int to[MAXN<<2],nxt[MAXN<<2],fst[MAXN],dis[MAXN],val[MAXN<<2],cnt;
23 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
24 int spfa(int s)
25 {
26     memset(inq,0,sizeof(inq));
27     memset(num,0,sizeof(num));
28     for(int i=1;i<=n;i++) dis[i]=inf;
29     dis[s]=0,q[l=r=1]=s;int x;
30     while(l<=r)
31     {
32         x=q[l++],inq[x]=0;
33         if(dis[s]<0) return 0;
34         for(int i=fst[x];i;i=nxt[i])
35             if(!vis[to[i]]&&dis[to[i]]>dis[x]+val[i])
36             {
37                 dis[to[i]]=dis[x]+val[i];
38                 if(!inq[to[i]])    q[++r]=to[i],inq[to[i]]=1;
39                 if(++num[to[i]]>n) return 0;
40             }
41     }
42     for(int i=1;i<=n;i++) vis[i]=vis[i]||num[i];
43     return 1;
44 }
45 int check()
46 {
47     for(int i=1;i<=n;i++)
48         if(!vis[i]) if(!spfa(i)) return 1;
49     return 0;
50 }
51 int main()
52 {
53     n=read(),m=read(),st=read();int a,b,c;
54     while(m--) {a=read(),b=read(),c=read();add(a,b,c);}
55     if(check()) {puts("-1");return 0;}
56     memset(vis,0,sizeof(vis));spfa(st);
57     for(int i=1;i<=n;i++)
58         if(dis[i]==inf) puts("NoPath");
59         else printf("%d
",dis[i]);
60 }

View Code