大致题意:
给出n个点的m条约束信息。每条信息表述为(P a b c)表示a在b北方距离c的位置,或者(V a b) 表示a在b北方1单位距离或者更远的位置。问是否可能存在符合以上m个要求的点。
大致思路:
把dis[i]设为其到始点的距离。第二个条件很简单dis[a]-dis[b]>=1 也就是dis[b]<=dis[a]-1。对于第一个,带等于号的条件dis[a]-dis[b]==c,我们可以转化为dis[a]-dis[b]>=c和dis[a]-dis[b]<=c 两个不等式,然后再转化为最短路三角不等式。由于所有点不一定互相连通,所以要设一个虚拟始点,与所有点相连,长度设为0。然后用spfa来判定是否有可行解即可~
擦擦擦,我用了大半年的spfa队列模版居然有bug,找了一夜bug才ac掉。真心草~泥~马了
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=200050;
const int mMax=1000050;
const int inf=1<<28;
struct{
int u,v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];
void addedge(int a,int b,int w){
edge[k].w = w;
edge[k].u=a;
edge[k].v=b;
edge[k].next=head[a];
head[a]=k;k++;
}
bool spfa(int s){ //始点,终点,总点数
int i, hhead = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方
for(i = 0; i <= n; i ++){
dis[i] = inf;////////////
vis[i] = false;
}
dis[s] = 0;
que[0] = s;
vis[s] = true;
while(tail != hhead){ // 循环队列实现。
int u = que[hhead];
vis[u] = false;
for(int p = head[u]; p != 0; p = edge[p].next){
int v = edge[p].v; // 写成了edge[k].v,WA了一晚。
if(dis[v] > dis[u] + edge[p].w){
dis[v] = dis[u] + edge[p].w;
if(!vis[v]){
vis[v] = true;
que[tail ++] = v;
if(tail == nMax) tail = 0;
if(++sum[v] > n) return false; // 不包含初始的进栈。
}
}
}
hhead ++;
if(hhead == nMax) hhead = 0;
}
return 1;
}
int main(){
int m,i,j,a,b,c,s;
char str[20];
while(cin>>n>>m){
s=0;
k=1;
memset(sum,0,sizeof(sum));
memset(head,0,sizeof(head));
while(m--){
scanf("%s",str);
if(str[0]=='P'){
scanf("%d%d%d",&a,&b,&c);
addedge(b,a,c);
addedge(a,b,-c);
}
else{
scanf("%d%d",&a,&b);
addedge(a,b,-1);
}
}
for(i=1;i<=n;i++){
addedge(s,i,0);
}
if (spfa(s))
printf("Reliable\n");
else
printf("Unreliable\n");
}
return 0;
}
分享到:
相关推荐
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1754756
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
这是西北工业大学的POJ试题的答案,欢迎下载!
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
poj分类poj分类poj分类poj分类
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj 百练 题目分类 poj 百练 题目分类
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj 1611 The Suspects 代码 并查集的应用
POJ题目分类POJ题目分类POJ题目分类
北大POJ1004-Financial Management 解题报告+AC代码
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
poj题目分类