尼玛的哪里错了。。
/* 在有向图上找一个环，使结点权值和/边权和的比例值最大 01规划，设比例为l，那么将每条边的权值改成a[u]-l*w，如果有正权环，则比例l可行 如何判图中存在正权环？将 权值存相反数，spfa判负环即可 复杂度elogans */ #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define maxn 1005 #define maxm 5005 #define esp 0.0000001 #define INF 0x3f3f3f3f struct Edge{int from,to,nxt,w;}edge[maxm],e[maxm]; int head[maxn],tot,a[maxn],n,m; void init(){ memset(head,-1,sizeof head); tot=0; } void addedge(int u,int v,int w){ edge[tot].from=u,e[tot].from=u; edge[tot].to=v,e[tot].to=v; edge[tot].nxt=head[u],e[tot].nxt=head[u]; edge[tot].w=w,head[u]=tot++; } double d[maxn]; int v[maxn],cnt[maxn]; int judge(double mid){ for(int i=0;i<tot;i++){ int u=edge[i].from; e[i].w=-(1.0*a[u]-mid*edge[i].w); } //spfa for(int i=1;i<=n;i++)d[i]=INF*1.0; memset(v,0,sizeof v); memset(cnt,0,sizeof cnt); d[1]=0;v[1]=1; queue<int>q; q.push(1);cnt[1]=1; while(!q.empty()){ int x=q.front();q.pop(); v[x]=0; for(int i=head[x];i!=-1;i=edge[i].nxt){ int y=edge[i].to,z=e[i].w; if(d[y]>d[x]+z){ d[y]=d[x]+z; if(v[y]==0)q.push(y),v[y]=1; if(++cnt[y]>n)return 1; } } } return 0; } int main(){ while(scanf("%d%d",&n,&m)==2){ init(); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } double l=0.0,r=100.0,mid; while(l+esp<=r){ mid=(l+r)/2; if(judge(mid))l=mid; else r=mid; } printf("%.2lf ",l); } return 0; }
下面这样的就没问题了。。
#include<cstdio> #include<cstring> #include<queue> #define eps 1e-3 #define MAXN 1010 using namespace std; struct T { int v; int w; int next; }edge[5005]; int cnt,head[MAXN]; void add_edge(int u,int v,int w) { edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } int n,m; int w[MAXN]; double dis[MAXN]; bool inque[MAXN]; int vis[MAXN]; bool SPFA(double R)//SPFA判断负权环 { queue<int> myque; memset(inque,0,sizeof inque); memset(vis,0,sizeof vis); for(int i = 1; i <= n; i++) dis[i] = 1e15; myque.push(1); dis[1] = 0; inque[1] = 1; vis[1]++; while(!myque.empty()) { int u = myque.front(); myque.pop(); inque[u] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; int y = edge[i].w; if(dis[u] + R*y - w[u] < dis[v]) { dis[v] = dis[u] + R*y - w[u]; if(!inque[v]) { myque.push(v); inque[v] = 1; vis[v]++; if(vis[v] > n) return 1; } } } } return 0; } int main() { memset(head,-1,sizeof head); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&w[i]); for(int i = 1; i <= m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); } double l = 0,r = 10000,mid; while(r - l > eps) { mid = (l+r)/2; if(SPFA(mid)) l = mid;//由于我们是把权值取反了的，因此题解中的R过大变成了R过小 else r = mid; } printf("%.2lf ",l); return 0; }