关系运算图。。。(差分约束)


给出一有向图,图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大于等于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 node
14 {
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     else
85     {
86         cout<<dis[n]<<endl;
87     }
88     return 0;
89 }
View Code

优质内容筛选与推荐>>
1、smarty 缓存用法简述(转)
2、mysql my.cnf 或my.ini配置文件参数解释(转):
3、PHP 多条件查询之简单租房系统
4、iphone天气插件------weathericon,安装,及其解决天气不变的方法!亲测!
5、final,static,this,super 关键字总结


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn