0x65 负环与差分约束
LB_tq
·
·
个人记录
Sightseeing Cows
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e3+10,M=1e4+10;
const double eps=1e-6;
struct Edge{
int nxt,ver,w;
}e[M];
int n,m,tot,hd[N],a[N],cnt[N];
double dis[N];
bool inq[N];
void add(int x,int y,int z){
tot++;
e[tot].nxt=hd[x];
e[tot].ver=y;
e[tot].w=z;
hd[x]=tot;
}
bool Check(double mid){
queue<int>q;
for(int i=1;i<=n;i++){
q.push(i);
inq[i]=1;
dis[i]=0,cnt[i]=0;
}
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=hd[u];i!=0;i=e[i].nxt){
int v=e[i].ver;
double z=mid*e[i].w-a[v];
if(dis[v]>dis[u]+z){
dis[v]=dis[u]+z;
if(!inq[v]){
cnt[v]++;
inq[v]=1;
q.push(v);
}
}
if(cnt[v]>=n)
return true;
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int x,y,z;
double l=0,r=0,mid;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add(x,y,z);
r+=z;
}
while(r-l>eps){
mid=(l+r)/2;
if(Check(mid))
l=mid;
else
r=mid;
}
printf("%.2f",l);
return 0;
}
```
# Intervals
解法 $1$ ：差分约束系统。建图跑最短路。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=5e4+10,M=1e6+10;
struct Edge{
int nxt,ver,w;
}e[M];
int n,m,tot,hd[N],dis[N];
bool inq[N];
void add(int x,int y,int z){
tot++;
e[tot].nxt=hd[x];
e[tot].ver=y;
e[tot].w=z;
hd[x]=tot;
}
void Spfa(){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
dis[m]=0;
inq[m]=1;
q.push(m);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=hd[u];i!=0;i=e[i].nxt){
int v=e[i].ver;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
}
}
}
int main(){
cin>>n;
int x,y,z;
for(int i=1;i<=n;i++){
cin>>x>>y>>z;
x++,y++;
m=max(m,y);
add(y,x-1,-z);
}
for(int i=1;i<=m;i++){
add(i,i-1,0);
add(i-1,i,1);
}
Spfa();
cout<<-dis[0];
return 0;
}
```
解法 $2$ ：数据结构优化贪心。发现需要快速完成三种操作：区间查询，单点修改，查询当前位置之前第一个空闲位置。于是可以使用树状数组和并查集维护。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e4+10;
struct Node{
int l,r,cnt;
}a[N];
int n,ans,fa[N],c[N];
bool vis[N];
bool cmp(Node x,Node y){
return x.r<y.r;
}
int lowbit(int x){
return x&(-x);
}
int Ask(int x){
if(!x)
return 0;
int res=0;
for(;x>0;x-=lowbit(x))
res+=c[x];
return res;
}
void Add(int x){
for(;x<N;x+=lowbit(x))
c[x]++;
}
int Getfa(int x){
if(x==fa[x])
return x;
return fa[x]=Getfa(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].cnt;
a[i].l++,a[i].r++;
}
sort(a+1,a+n+1,cmp);
for(int i=0;i<N;i++)
fa[i]=i;
for(int i=1;i<=n;i++){
int x=a[i].cnt;
x-=(Ask(a[i].r)-Ask(a[i].l-1));
int t=Getfa(a[i].r);
while(x>0){
Add(t);
x--,ans++;
fa[t]=t-1;
t=Getfa(t);
}
}
cout<<ans;
return 0;
}
```