【poj 3385】【模板】负环

题目描述

暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索

输入输出格式

输入格式：

第一行一个正整数T表示数据组数，对于每组数据：

第一行两个正整数N M，表示图有N个顶点，M条边

接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）

输出格式：

共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。

输入输出样例

输入样例#1：

输出样例#1：

N0
YE5

说明

N,M,|w|≤200 000；1≤a,b≤N；T≤10 建议复制输出格式中的字符串。

此题普通Bellman-Ford或BFS-SPFA会TLE

题解

注意有两个个坑点，当然我都被坑到了。//脸红

1.无向边和双向边的问题，所以边数会需要乘二。

2.输出的是YE'5'和N'0'（均不含单引号）。

1.利用BellmanFord判负环。

　　如果不存在负环的话，那么最多经过N - 1次迭代就可以得到最短路。因为形成最短路最多N - 1个节点（起点不算），但是如果存在了负环，那么就可以一直迭代，最短路会越来越小。可以利用这个性质来判断是否存在负环。（此题会挂）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 200005
 6 using namespace std;
 7 int read(){
 8     int x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int t,n,m,d[maxn],cnt;
14 struct node{
15     int from,to,cost;
16 }e[maxn*2];
17 bool BF(int sta){
18     for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
19     d[sta]=0;
20     for(int i=1;i<n;i++){
21         bool flag=false;
22         for(int j=1;j<=cnt-1;j++){
23             if(d[e[j].to]>(d[e[j].from]+e[j].cost)){
24                 flag=true;
25                 d[e[j].to]=d[e[j].from]+e[j].cost;
26             }
27         }
28         if(!flag) break;
29     }
30     for(int i=1;i<=cnt-1;i++)
31         if(d[e[i].to]>(d[e[i].from]+e[i].cost))
32             return false;
33     return true;
34 }
35 int main(){
36     t=read();
37     while(t--){
38         cnt=1;
39         memset(e,0,sizeof(e));
40         n=read(),m=read();
41         for(int i=1;i<=m;i++){
42             int u=read(),v=read(),w=read();
43             if(w>=0){
44                 e[cnt].to=v;e[cnt].from=u;e[cnt++].cost=w;
45                 e[cnt].to=u;e[cnt].from=v;e[cnt++].cost=w;
46             }
47             else if(w<0)e[cnt].to=v;e[cnt].from=u;e[cnt++].cost=w;
48         }
49         if(BF(1)) printf("N0
");
50         else printf("YE5
");
51     }
52     return 0;
53 }

2.利用spfa判负环。

　　1.记录松弛次数，超过n则证明存在负环。（会TLE）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 200005
 7 #define inf 0x3f3f3f3f
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int t,n,m,d[maxn],cnt,inq[maxn],last[maxn],times[maxn];
16 struct node{
17     int next,to,cost;
18 }e[maxn*2];
19 void add(int u,int v,int w){
20     e[++cnt].to=v;e[cnt].next=last[u];e[cnt].cost=w;last[u]=cnt;
21 }
22 bool spfa(int s,int t){
23     queue<int> q;
24     q.push(s);
25     d[s]=0;inq[s]=1;times[s]++;
26     while(!q.empty()){
27         int u=q.front();q.pop();
28         inq[u]=0;
29         for(int i=last[u];i;i=e[i].next){
30             if(d[e[i].to]>d[u]+e[i].cost){
31                 d[e[i].to]=d[u]+e[i].cost;
32                 if(!inq[e[i].to]){
33                     inq[e[i].to]=1;
34                     q.push(e[i].to);
35                     times[e[i].to]++;
36                     if(times[e[i].to]>n) return false;
37                 }
38             }
39         }
40     }
41     return true;
42 }
43 int main(){
44     t=read();
45     while(t--){
46         n=read(),m=read();
47         cnt=0;
48         memset(last,0,sizeof(last));
49         memset(inq,0,sizeof(inq));
50         memset(d,inf,sizeof(d));
51         memset(times,0,sizeof(times));
52         for(int i=1;i<=m;i++){
53             int u=read(),v=read(),w=read();
54             if(w>=0) add(u,v,w),add(v,u,w);
55             else if(w<0) add(u,v,w);
56         }
57         if(spfa(1,n)) printf("N0
");
58         else printf("YE5
");
59     }
60     return 0;
61 }

　　2.后来想了想，因为我们只需要判断负环，相当于我们需要找到一条权值和为负的回路，那不妨使距离数组d初始化为0。这样处理后，第一次拓展只会拓展到与起点相连边权为负的边。那么我们就分别枚举所有的点作为起点，如果已经找到一个负环就不再继续枚举。根据SPFA，我们找到的负环一定包含当前枚举的这个点（因为这个点出现了两次）。（AC）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 200005
 7 #define inf 0x3f3f3f3f
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 bool flag;
16 int t,n,m,d[maxn],cnt,inq[maxn],last[maxn],vis[maxn];
17 struct node{
18     int next,to,cost;
19 }e[maxn*2];
20 void add(int u,int v,int w){
21     e[++cnt].to=v;e[cnt].next=last[u];e[cnt].cost=w;last[u]=cnt;
22 }
23 void dfs_spfa(int s){
24     if(flag)  return ;
25     vis[s]=true;
26     for(int i=last[s];i;i=e[i].next){
27         if(flag) return ;
28         int v=e[i].to;
29         if(d[s]+e[i].cost<d[v]){
30             d[v]=d[s]+e[i].cost;
31             if(vis[v]){
32                 flag=true;
33                 return ;
34             }
35             else dfs_spfa(v);
36         }
37     }
38     vis[s]=false;
39 }
40 int main(){
41     t=read();
42     while(t--){
43         n=read(),m=read();
44         cnt=0;
45         memset(last,0,sizeof(last));
46         memset(d,0,sizeof(d));
47         memset(vis,0,sizeof(vis));
48         for(int i=1;i<=m;i++){
49             int u=read(),v=read(),w=read();
50             if(w>=0) add(u,v,w),add(v,u,w);
51             else if(w<0) add(u,v,w);
52         }
53         flag=false;
54         for(int i=1;i<=n;i++){
55             dfs_spfa(i);
56             if(flag) break;
57         }
58         if(flag) printf("YE5
");
59         else printf("N0
");
60     }
61     return 0;
62 }