首页 > 代码库 > 关系运算图。。。（差分约束）
关系运算图。。。（差分约束）
给出一有向图，图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k，则求最小的k，若任何k都无法满足则输出NO。
例如下表中最小的k为2。
结点1>结点2
结点2>结点3
结点2>结点4
结点3=结点4
如果存在这样的k，输出最小的k值；否则输出‘NO’。
INTPUT：
共二行，第一行有二个空格隔开的整数n和m。n表示G的结点个数，m表示G的边数，其中1<=n<=1000, 0<=m<=10000。全部结点用1到n标出，图中任何二点之间最多只有一条边，且不存在自环。
第二行共有3m个用空格隔开的整数，第3i-2和第3i-1（1<=i<=m）个数表示第i条边的顶点。第3i个数表示第i条边上的符号，其值用集合{-1，0，1}中的数表示：-1表示‘<’, 0 表示‘=’, 1表示‘>’。
4 4
1 2 -1 2 3 0 2 4 -1 3 4 -1
OUTPUT：
仅一行，如无解则输出‘NO’；否则输出最小的k的值。
2
这道题需要另一个技能————差分约束。
思路：
题中有三个约束条件：a<b,a=b,a>b;
但实际上只有两种：a<b,a=b;
所以，对于a<b,我们就让a向b有一条权值为1的边。a>b，就让b到a有一条权值为1的边。
a=b，a到b有一条权值为0的边。
然后，SPFA求最大路。
cpp：
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<iomanip> 8 #include<queue> 9 using namespace std;10 int n,m;11 int len=0,dis[30000],lin[30000];12 int id[30000];13 struct node14 {15 int x,y,v;16 }e[30000];17 18 void init(int xx,int yy,int vv)19 {20 e[++len].y=lin[xx];lin[xx]=len;e[len].x=yy;e[len].v=vv;21 }22 23 bool pai()24 {25 /*memset(dis,0,sizeof(dis));*/26 int q[30000];27 int head=0,tail=0;28 int maxx=0;29 for(int i=1;i<=n;i++)30 if(id[i]==0) q[++tail]=i;31 while(head<=tail)32 {33 int tn=q[++head];34 int te=lin[tn];35 for(int i=te;i;i=e[i].y)36 {37 int tmp=e[i].x;38 id[tmp]--;39 if(id[e[i].x]<0)40 return 1;41 dis[tmp]=max(dis[tmp],dis[q[head]]+e[i].v);42 if(id[e[i].x]==0)43 q[++tail]=e[i].x;44 }45 }46 sort(dis+1,dis+1+n);47 if(dis[n]<=maxx)48 return 1;49 return 0;50 }51 52 int main()53 {54 freopen("2.in","r",stdin);55 freopen("2.out","w",stdout);56 //ios::sync_with_stdio(false);57 cin>>n>>m;58 memset(e,0,sizeof(e));59 memset(id,0,sizeof(id));60 /*for(int i=1;i<=n;i++)61 init(0,i,0);*/62 for(int i=1;i<=m;i++)63 {64 int xx,yy,vv;65 cin>>xx>>yy>>vv;66 if(vv==0)67 {68 init(xx,yy,0);69 id[yy]++;70 }71 else if(vv==1)72 {73 init(yy,xx,1);74 id[xx]++;75 }76 else if(vv==-1)77 {78 init(xx,yy,1);79 id[yy]++;80 }81 }82 if(pai())83 cout<<"NO"<<endl;84 else85 {86 cout<<dis[n]<<endl;87 }88 return 0;89 }
关系运算图。。。（差分约束）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。