[bzoj1731] [Usaco2005 dec]Layout 排队布局

时间:2023-03-09 18:56:07
[bzoj1731]  [Usaco2005 dec]Layout 排队布局

  差分约束系统。。。因为题目要求的是1和n的最大距离所以这题就跑最长路。。

  对于互相反感的牛(i与j互相反感,彼此距离至少为len,i<j),就有dis[j]-dis[i]>=len。就加一条i->j,长度为len的边。

  有好感的牛(i与j有好感,彼此距离至多len,i<j),就有dis[j]-dis[i]<=len;但因为我们跑的是最长路,所以得改成dis[i]-dis[j]>=-len的形式,就加一条j->i,长度-len的边。

  又因为牛是按编号站成一列。。所以dis[i+1]-dis[i]>=0。也就是连一条i->i+1,长度为0的边(1<=i<n)。

  如果有正权环的话就无解,如果从点n无法走到点1,也就是说n和1之间没有什么约束,那么1和n距离可以无穷大。。。

  其实也可以把权值取反然后跑最短路。。虽然都一样= =

 #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
struct zs{
int too,pre,dis;
}e[];
int last[maxn],dis[maxn],dl[maxn],tot;
int i,n,m1,m2,a,b,c,l,r,now;
bool u[maxn],ins[maxn],flag;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline void insert(int a,int b,int c){
e[++tot].too=b;e[tot].dis=c;e[tot].pre=last[a];last[a]=tot;
}
void dfs(int x){
ins[x]=;
for(int i=last[x],to=e[i].too;i&&!flag;i=e[i].pre,to=e[i].too)if(dis[to]<dis[x]+e[i].dis){
dis[to]=dis[x]+e[i].dis;if(ins[to]){flag=;return;}
dfs(to);
}
ins[x]=;
}
int main(){
n=read();m1=read();m2=read();
for(i=;i<n;i++)insert(i,i+,);
for(i=;i<=m1;i++){
a=read();b=read();c=read();
if(a>b)swap(a,b);
insert(b,a,-c);
}
for(i=;i<=m2;i++){
a=read();b=read();c=read();if(a>b)swap(a,b);
insert(a,b,c);
}
l=;r=;dl[]=n;u[n]=;
while(l<r){
now=dl[++l];
for(i=last[now];i;i=e[i].pre)if(!u[e[i].too])
dl[++r]=e[i].too,u[e[i].too]=;
}
if(!u[]){puts("-2");return ;}
memset(dis,,sizeof(dis));dis[n]=;
dfs(n);
if(flag){puts("-1");return ;}
printf("%d\n",-dis[]);
return ;
}

  为啥dfs版的spfa会比kpm写的队列版慢20倍。。。。。。。。。。。也许是数据很少有无解情况吧。。