列队(line)

【一句话题意】给定一个一维坐标轴和n个点。再给定m个两点之间的关系。如果关系有矛盾，则输出impossible；如果没有矛盾则输出最左点和最右点的坐标差。
【分析】这道题可以用带权并查集做，道理与之前的方块消除相同，这里不再赘述。

另一方面这道题也可以用差分约束系统的弱化版解决。
关于差分约束系统，本质是把几个不等式组的最值求解转化为图论问题。
对于 x i − x j < = a i , j x_i-x_j<=a_{i,j} xi​−xj​<=ai,j​可以转化为 x i < = x j + a i , j x_i<=x_j+a_{i,j} xi​<=xj​+ai,j​相当于，在 x j x_j xj​到 x i x_i xi​的方向上连接一条权值为 a i , j a_{i,j} ai,j​的边。当有多条边时可以跑一遍spfa求各个 x i x_i xi​的最小值即可。如果存在正环或负环，则无解。
对于这道题，两点之间的相对位置是固定的，所以可以直接把不等号变成等号，双向建边。先确定某个点的值，再将未确定的点跑一遍spfa，如果一个点有两个不同的位置，则存在矛盾。

#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+1000;
struct node{int v,nxt,c;
}edge[maxn<<2];
int head[maxn],tot;
int vis[maxn],dist[maxn];
int n,m,len=0;
inline void read(int &x){x=0;int fl=1;char tmp=getchar();while(tmp<'0'||tmp>'9'){if(tmp=='-')fl=-fl;tmp=getchar();}while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();x*=fl;
}
inline void add_edge(int x,int y,int c){edge[tot].nxt=head[x];edge[tot].v=y;edge[tot].c=c;head[x]=tot++;
}
inline bool spfa(int x){int maxx=0,minn=0;dist[x]=0,vis[x]=1;queue<int>q;q.push(x);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].v;if(!vis[v]){dist[v]=dist[u]+edge[i].c;maxx=max(dist[v],maxx);minn=min(dist[v],minn);vis[v]=1;q.push(v);}else if(dist[v]!=dist[u]+edge[i].c)return false;}}len=max(len,maxx-minn);return true;
}
int main(){freopen("line.in","r",stdin);freopen("line.out","w",stdout);memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));cin>>n>>m;for(int i=1;i<=m;i++){int l,r,d;read(l),read(r),read(d);add_edge(l,r,d);add_edge(r,l,-d);}for(int i=1;i<=n;i++){if(!vis[i]){if(!spfa(i)){printf("impossible\n");return 0;}}}printf("%d\n",len);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！