首页 > 代码库 > Bzoj4773 负环

Bzoj4773 负环

2024-09-11 00:47:01   220人阅读

Time Limit: 100 Sec  Memory Limit: 256 MB
Submit: 194  Solved: 97

Description

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得
环上的边权和为负数。保证图中不包含重边和自环。
 
 

 

Input

第1两个整数n, m,表示图的点数和边数。
接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。
2 <= n <= 300
0 <= m <= n(n <= 1)
1 <= ui, vi <= n
|wi| <= 10^4
 

 

Output

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。
 

 

Sample Input

3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

Sample Output

2

HINT

 

Source

二分答案判负环

用倍增什么的搞一搞就好了。

然而试图用SPFA水过去的时候发现我可能连SPFA都不会写了

 

技术分享
 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 struct edge{17     int v,nxt,w;18 }e[mxn<<1];19 int hd[mxn],mct=0;20 void add_edge(int u,int v,int w){21     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return;22 }23 int lim;24 int inq[mxn],dis[mxn];25 bool SPFA(int u,int time){26     if(inq[u])return 1;27     if(time>lim)return 0;28     inq[u]=1;29     for(int i=hd[u];i;i=e[i].nxt){30         int v=e[i].v;31         if(dis[v]>=dis[u]+e[i].w){32             dis[v]=dis[u]+e[i].w;33             if(SPFA(v,time+1))return 1;34         }35     }36     inq[u]=0;37     return 0;38 }39 int n,m;40 bool chk(){41     for(int i=1;i<=n;i++){42         memset(dis,0x3f,sizeof dis);43         memset(inq,0,sizeof inq);44         if(SPFA(i,1))return 1;45     }46     return 0;47 }48 void solve(){49     int l=1,r=n;50     int res=0;51     while(l<=r){52         int mid=(l+r)>>1;53         lim=mid;54         memset(inq,0,sizeof inq);55         if(chk()){56             res=mid;57             r=mid-1;58         }59         else l=mid+1;60     }61     printf("%d\n",res);62     return;63 }64 int main(){65     int i,j,u,v,w;66     n=read();m=read();67     for(i=1;i<=m;i++){68         u=read();v=read();w=read();69         add_edge(u,v,w);70     }71     solve();72     return 0;73 }
WA

为啥会错啊……

 

非要把inq放在循环里面才能过……

——————updated

仔细想想好像确实是这样，起初的u并没有被更新过就直接入队，会导致不必要的错误。

但是循环枚举起点的时候把dis[i]设成0，也过不了，无限TLE。

大概理解还是不透彻

——————

技术分享
 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=310;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 struct edge{17     int v,nxt,w;18 }e[mxn*mxn];19 int hd[mxn],mct=0;20 void add_edge(int u,int v,int w){21     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return;22 }23 int lim;24 int inq[mxn],dis[mxn];25 bool SPFA(int u,int time){26     for(int i=hd[u];i;i=e[i].nxt){27         int v=e[i].v;28         if(dis[v]>=dis[u]+e[i].w){29             if(inq[v])return 1;30             if(time==lim)return 0;31             dis[v]=dis[u]+e[i].w;32             inq[v]=1;33             if(SPFA(v,time+1))return 1;34             inq[v]=0;35         }36     }37     return 0;38 }39 int n,m;40 bool chk(){41     for(int i=1;i<=n;i++){42         memset(dis,0,sizeof dis);43         memset(inq,0,sizeof inq);44         dis[i]=0;inq[i]=1;45         if(SPFA(i,1))return 1;46     }47     return 0;48 }49 void solve(){50     int l=1,r=n;51     int res=0;52     while(l<=r){53         int mid=(l+r)>>1;54         lim=mid;55         memset(inq,0,sizeof inq);56         if(chk()){57             res=mid;58             r=mid-1;59         }60         else l=mid+1;61     }62     printf("%d\n",res);63     return;64 }65 int main(){66     int i,j,u,v,w;67     n=read();m=read();68     for(i=1;i<=m;i++){69         u=read();v=read();w=read();70         add_edge(u,v,w);71     }72     solve();73     return 0;74 }
AC

 

Bzoj4773 负环


联系
我们