首页 > 代码库 > COGS1117

COGS1117

2024-08-11 16:48:18   219人阅读

传送门：

差分约束第一题。

 

所有的条件无非两种不等式

d[i]-d[j]>=dist

d[i]-d[j]<=dist

然后进行变形

d[i]-d[j]>=dist    =>  d[j]<=d[i]-dist  => insert(i,j,-dist)

d[i]-d[j]<=dist    =>  d[i]<=d[j]+dist   => insert(j,i,dist)  

d[i]+0>=d[i-1]    =>  insert(i,i-1,0)

由此可以建图

 

最后需要注意两个点：

1.如何判断-1？

-1是无解的情况，什么是无解?显然是存在负环的情况。

2.如何判断-2？

当ans==oo时，就应输出-2，因为如果最小的距离是无穷大那么显然取任何值都可以。

 

技术分享
 1 //COGS 1117 2 //by Cydiater 3 //2016.9.1 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <algorithm>10 #include <queue>11 #include <map>12 #include <iomanip>13 #include <cmath>14 #include <ctime>15 using namespace std;16 #define ll long long17 #define up(i,j,n)        for(int i=j;i<=n;i++)18 #define down(i,j,n)        for(int i=j;i>=n;i--)19 #define FILE "layout"20 const int MAXN=1e5+5;21 const int oo=0x3f3f3f3f;22 inline ll read(){23     char ch=getchar();ll x=0,f=1;24     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26     return x*f;27 }28 ll N,Ma,Mb,LINK[MAXN],len=0,head,tail,q[MAXN],dis[MAXN],cnt[MAXN];29 bool vis[MAXN];30 struct edge{31     int y,next,v;32 }e[MAXN];33 namespace solution{34     inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}35     void init(){36         N=read();Ma=read();Mb=read();37         up(i,1,Ma){38             ll x=read(),y=read(),dist=read();39             if(x>y)swap(x,y);40             insert(x,y,dist);41         }42         up(i,1,Mb){43             int x=read(),y=read(),dist=read();44             if(x>y)swap(x,y);45             insert(y,x,-dist);46         }47         up(i,2,N)insert(i,i-1,0);48     }49     void SPFA(){50         memset(vis,0,sizeof(vis));51         memset(cnt,0,sizeof(cnt));52         up(i,1,N)dis[i]=oo;53         dis[1]=0;vis[1]=1;54         head=1;tail=0;q[++tail]=1;55         for(;head<=tail;head++){56             int node=q[head];57             for(int i=LINK[node];i;i=e[i].next)58                 if(dis[e[i].y]>dis[node]+e[i].v){59                     dis[e[i].y]=dis[node]+e[i].v;60                     if(!vis[e[i].y]){61                         if(cnt[e[i].y]==N){62                             puts("-1");63                             exit(0);64                         }65                         cnt[e[i].y]++;66                         q[++tail]=e[i].y;67                         vis[e[i].y]=1;68                     }69                 }70             vis[node]=0;71         }72     }73     void output(){74         if(dis[N]==oo)dis[N]=-2;75         cout<<dis[N]<<endl;76     }77 }78 int main(){79     //freopen(FILE".in","r",stdin);80     //freopen(FILE".out","w",stdout);81     //freopen("input.in","r",stdin);82     using namespace solution;83     init();84     SPFA();85     output();86     return 0;87 }
View Code

 

COGS1117


联系
我们