3.7 负环
3.7.1 904. 虫洞
代码：
#include<bits/stdc++.h> using namespace std; const int N=510,M=6010; int F,n,m,W; int h[N],e[M],w[M],ne[M],idx; int dis[N]; bool st[N]; int cnt[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { memset(cnt,0,sizeof cnt); memset(dis,0x3f,sizeof dis); dis[1]=0; queue<int> q; for(int i=1;i<=n;i++) { q.push(i); st[i]=true; } while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { ios::sync_with_stdio(0); cin>>F; while(F--) { memset(h,-1,sizeof h); idx=0; cin>>n>>m>>W; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } for(int i=0;i<W;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,-c); } if(spfa()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
3.7.2 361. 观光奶牛
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010,M=5010; int n,m; int wf[N]; double dis[N]; bool st[N]; int cnt[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool check(double mid) { memset(dis,0,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int> q; for(int i=1;i<=n;i++) { q.push(i); st[i]=true; } while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]<dis[t]+wf[t]-mid*w[i]) { dis[j]=dis[t]+wf[t]-mid*w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=1;i<=n;i++) cin>>wf[i]; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } double l=0,r=1010; while(r-l>1e-4) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2f",r); return 0; }
3.7.3 1165. 单词环
代码：
#include<bits/stdc++.h> using namespace std; const int N=700,M=100010; int n; double dis[N]; bool st[N]; int cnt[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool check(double mid) { memset(dis,0,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int> q; for(int i=0;i<n;i++) { q.push(i); st[i]=true; } int sum=0; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]<dis[t]+w[i]-mid) { dis[j]=dis[t]+w[i]-mid; cnt[j]=cnt[t]+1; sum++; if(cnt[j]>=n) return true; if(sum>4*n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { while(true) { memset(h,-1,sizeof h); cin>>n; if(n==0) break; for(int i=1;i<=n;i++) { string str; cin>>str; int len=str.length(); if(len<2) continue; string left=str.substr(0,2),right=str.substr(len-2); int a=(left[0]-'a')*26+left[1]-'a',b=(right[0]-'a')*26+right[1]-'a'; add(a,b,len); } n=26*26; if(check(0)) { double l=0,r=1010; while(r-l>1e-4) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2f\n",r); } else cout<<"No solution"<<endl; } return 0; }
3.8 差分约束
3.8.1 1169. 糖果
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=100010,M=300010; int n,m; LL dis[N]; int cnt[N]; bool st[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { memset(dis,-0x3f,sizeof dis); dis[0]=0; stack<int> q; q.push(0); st[0]=true; int sum=0; while(q.size()) { int t=q.top(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]<dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; sum++; if(sum>10*n) return false; if(cnt[j]>=n+1) return false; if(!st[j]) { q.push(j); st[j]=true; } } } } return true; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i<m;i++) { int x,a,b; cin>>x>>a>>b; if(x==1) add(a,b,0),add(b,a,0); else if(x==2) add(a,b,1); else if(x==3) add(b,a,0); else if(x==4) add(b,a,1); else add(a,b,0); } for(int i=1;i<=n;i++) add(0,i,1); if(!spfa()) { cout<<-1<<endl; } else { LL res=0; for(int i=1;i<=n;i++) res+=dis[i]; cout<<res; } return 0; }
3.8.2 362. 区间
代码：
#include<bits/stdc++.h> using namespace std; const int N=50010,M=150010; int n; int dis[N]; bool st[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void spfa() { memset(dis,-0x3f,sizeof dis); dis[0]=0; queue<int> q; q.push(0); while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]<dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } } int main() { memset(h,-1,sizeof h); cin>>n; for(int i=1;i<=50001;i++) { add(i-1,i,0); add(i,i-1,-1); } for(int i=0;i<n;i++) { int a,b,c; cin>>a>>b>>c; a++,b++; add(a-1,b,c); } spfa(); cout<<dis[50001]; return 0; }
3.8.3 1170. 排队布局
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010,M=30010; int n,L,D; int dis[N],cnt[N]; bool st[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(int x) { memset(dis,0x3f,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int> q; for(int i=1;i<=x;i++) { q.push(i); dis[i]=0; st[i]=true; } while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { memset(h,-1,sizeof h); cin>>n>>L>>D; for(int i=1;i<n;i++) add(i+1,i,0); for(int i=0;i<L;i++) { int a,b,c; cin>>a>>b>>c; int _min=min(a,b),_max=max(a,b); add(_min,_max,c); } for(int i=0;i<D;i++) { int a,b,c; cin>>a>>b>>c; int _min=min(a,b),_max=max(a,b); add(_max,_min,-c); } if(spfa(n)) cout<<-1<<endl; else { spfa(1); if(dis[n]==0x3f3f3f3f) cout<<-2<<endl; else cout<<dis[n]<<endl; } return 0; }
3.8.4 393. 雇佣收银员
代码：
#include<bits/stdc++.h> using namespace std; const int N=30,M=100; int n; int dis[N],cnt[N]; int r[N],num[N]; bool st[N]; int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void build(int c) { memset(h,-1,sizeof h); idx=0; for(int i=1;i<=24;i++) { add(i-1,i,0); add(i,i-1,-num[i]); } for(int i=1;i<=7;i++) add(i+16,i,r[i]-c); for(int i=8;i<=24;i++) add(i-8,i,r[i]); add(0,24,c),add(24,0,-c); } bool spfa(int c) { build(c); memset(dis,-0x3f,sizeof dis); memset(cnt,0,sizeof cnt); memset(st,0,sizeof st); queue<int> q; q.push(0); dis[0]=0; st[0]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]<dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=25) return false; if(!st[j]) { q.push(j); st[j]=true; } } } } return true; } int main() { int T; cin>>T; while(T--) { for(int i=1;i<=24;i++) cin>>r[i]; cin>>n; memset(num,0,sizeof num); for(int i=0;i<n;i++) { int t; cin>>t; num[t+1]++; } bool success=false; for(int i=0;i<=1000;i++) { if(spfa(i)) { cout<<i<<endl; success=true; break; } } if(!success) cout<<"No Solution"<<endl; } return 0; }
