首页技术正文

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

程序员子超技术 2022年11月16日

0 收藏 577 点赞 3,353 浏览 1500 个字

　　差分约束系统。。。因为题目要求的是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 ;
 }