差分约束专题

自用笔记算法

差分约束专题

uva 11671

转跳链接

uva 11478

题目要求

白书P334
给定一个有向图 每条边都有一个权值 每次你可以选择一个结点v和一个整数d 把所有以v为终点的边的权值减小d 把所有以v为起点的边的权值增加d
最后要让所有边的最小值非负且尽量大

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];
  int d[maxn];
  int p[maxn];
  int cnt[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = inf; inq[i] = true; Q.push(i); }
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
bool test(int x){
    for(int i=0;i<sp.m;i++) sp.edges[i].dist-=x;
    bool ans=sp.negativeCycle();
    for(int i=0;i<sp.m;i++) sp.edges[i].dist+=x;
    return !ans;
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        sp.init(n+1);
        int Max=0;
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            Max=max(Max,w);
            sp.AddEdge(u,v,w);
        }
        if(test(Max+1)) puts("Infinite");
        else if(!test(1)) puts("No Solution");
        else{
            int l=1,r=Max,ans=1;
            while(l<=r){
                int mid=l+r>>1;
                if(test(mid)) ans=mid,l=mid+1;
                else r=mid-1;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

思路

白书P334
令sum(x)为作用在x结点上的所有d之和
对于每一条边可以列出不等式sum(b)-sum(a)<=w(a,b)-x 这实际是一个差分约束系统
对应-x操作只需要每次-x后判断再还原即可
如果所有结点都可以加到Max+1 说明所有结点都增加了 那么再执行一次还会增加直到infinite 所以输出infinite
如果二分到最小的答案1都不能满足条件 说明无解
否则二分出ans即可

HDU 1384

题目要求

给出n个区间 每个区间有个权值Ci 最终找出一个最少的数字的集合 使得满足每个区间中至少包含Ci个数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
#define maxn 50050
#define inf 0x3f3f3f3f
using namespace std;
int n;
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];
  int d[maxn];
  int p[maxn];
  int cnt[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle(int s) {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    memset(d,-inf,sizeof d);
    inq[s]=true;
    Q.push(s);
    d[s]=0;
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] < d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        sp.init(maxn);
        int L=inf,R=0;
        for(int i=1;i<=n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            u++,v++;
            L=min(L,u-1);
            R=max(R,v);
            sp.AddEdge(u-1,v,w);
        }
        for(int i=L;i<=R;i++){
            sp.AddEdge(i-1,i,0);
            sp.AddEdge(i,i-1,-1);
        }
        sp.negativeCycle(L);
        printf("%d\n",sp.d[R]);
    }
    return 0;
}

思路

坐标上的每个点看作图中的一个点
sum[i]表示前i个元素中包含的数字个数 那么a到b含有的数字个数可以表示为sum[b]-sum[a-1]
根据题目条件可得sum[b]-sum[a-1]>=w
由于题目求的是S的最小数量 所以不等式建>= spfa求最长路
另外题目还有2个隐含的条件sum[i]-sum[i-1]<=1 && sum[i]-sum[i-1]>=0 化成>=后建图
注意：
1.本题题目未说明不存在的情况 所以spfa里判负圈其实是多余的
2.由于ai和bi的下限是0 减1后可能越界 所以均加1 L记录的左边界也要对应的减1
3.本题要记录L和R 在L和R内进行建图
4.本题是有源有汇的spfa问题 所以要带入L点 输出d[R]

HDU 1529

题目要求

给出一天中24个小时，每个小时至少需要的工人数，有m个工人，每个工人有其开始时间，每个工人持续工作8小时。求出完成一天的工作最少需要多少人

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define maxn 30
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n;
int val[maxn],num[maxn];
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = -inf; inq[i] = true; Q.push(i); }
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] < d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        mm(val,0),mm(num,0);
        for(int i=1;i<=24;i++) scanf("%d",&val[i]);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            x++;
            num[x]++;
        }
        int l=0,r=n,ans=inf;
        while(l<=r){
            int mid=l+r>>1;
            sp.init(maxn);
            sp.n=25;
            for(int i=1;i<=24;i++){
                sp.AddEdge(i,i-1,-num[i]);
                sp.AddEdge(i-1,i,0);
            }
            for(int i=8;i<=24;i++) sp.AddEdge(i-8,i,val[i]);
            for(int i=1;i<8;i++) sp.AddEdge(i+16,i,val[i]-mid);
            sp.AddEdge(0,24,mid);
            if(!sp.negativeCycle()) ans=mid,r=mid-1;
            else l=mid+1;
        }
        if(ans==inf) puts("No Solution");
        else printf("%d\n",ans);
    }
	return 0;
}

思路

转跳链接第二题
注意：
1.无需设0为超级汇点 spfa直接所有点入队即可
2.判负圈的n应该为25个点
3.因为本题的n比较小 所以暴力和二分都没有问题
本题跟上题的区别在于：
上题是选择最少的点满足对区间的限制 本题是选择最少的点满足对点的限制 本质一样 只需把sum[b]-sum[a-1]换成sum[i]-sum[i-1]即可转换成对点的限制
另外本题由于有一个工作8小时的条件 所以多了几个方程的限制 必须找到这些隐含的条件

HDU 1531

题目要求

大概就是要部分的和满足一个约束条件

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define maxn 250
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m;
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = inf; inq[i] = true; Q.push(i); }
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)){
		if(n==0) break;
		scanf("%d",&m);
		sp.init(maxn); 
		sp.n=n+1;
		for(int i=1;i<=m;i++){
			int u,v,k;
			char op[10];
			scanf("%d%d%s%d",&u,&v,op,&k);
			if(op[0]=='g') sp.AddEdge(u+v,u-1,-k-1);
			else sp.AddEdge(u-1,u+v,k-1);
		}
		if(sp.negativeCycle()) puts("successful conspiracy");
		else puts("lamentable kingdom");
	}
	return 0;
}

思路

设s[i] = a[1] + a[2] + …… + a[i];
a[Si] + a[Si+1] + … + a[Si+ni] = s[Si+ni] - s[Si-1]；
所以由题意有：
①s[Si+ni] - s[Si-1] > ki
或②s[Si+ni] - s[Si-1] < ki
由于只是检验是否有解，所以最短路或最长路都可用，以下是最短路要建立的关系：
把①化为：s[si-1] - s[si+ni] <= - ki - 1
把②化为：s[si+ni] - s[si-1] <= ki - 1

HDU 1534

题目要求

有n个项目 每个项目有需要的工作时间
FAS表示第一个项目的结束时间必须在第二个的开始时间之后
FAF表示第一个项目的结束时间必须在第二个的结束时间之后
SAS表示第一个项目的开始时间必须在第二个的开始时间之后
SAF表示第一个项目的开始时间必须在第二个的结束时间之后
问给出n个计划的开始时间 使得总时间最短 若无解输出impossible

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define maxn 10050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
int last[maxn];
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle(int s) {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    mm(d,-inf);
    inq[s]=true;
    d[s]=0;
    Q.push(s);
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] < d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
char op[10];
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		sp.init(maxn);
		sp.n=n+1;
		for(int i=1;i<=n;i++) scanf("%d",&last[i]);
		while(scanf("%s",op)){
			if(op[0]=='#') break;
			int u,v;
			scanf("%d%d",&u,&v);
			if(op[0]=='S' && op[2]=='S') sp.AddEdge(v,u,0);
			else if(op[0]=='F' && op[2]=='S') sp.AddEdge(v,u,-last[u]);
			else if(op[0]=='S' && op[2]=='F') sp.AddEdge(v,u,last[v]);
			else if(op[0]=='F' && op[2]=='F') sp.AddEdge(v,u,last[v]-last[u]);
		}
		for(int i=1;i<=n;i++) sp.AddEdge(0,i,0);
		printf("Case %d:\n",Case++);
		if(sp.negativeCycle(0)) puts("impossible");
		else{
			for(int i=1;i<=n;i++) printf("%d %d\n",i,sp.d[i]);
		}
		puts("");
	}
	return 0;
}

思路

求最短距离 所以不等式建>= 跑最长路
设第i项工作持续时间为v[i]，开始时间s[i]，那么结束时间就是s[i]+v[i]
SAS: s[a] >= s[b] —> s[a] - s[b] >= 0
FAS: s[a] + v[a] >= s[b] —> s[a] - s[b] >= -v[a]
SAF: s[a] >= s[b] + v[b] —> s[a] - s[b] >= v[b]
FAF: s[a] + v[a] >= s[b] + v[b] —> s[a] - s[b] >= v[b] - v[a]
因为本题的开始时间为0 所以建一个超级源点S=0 向所有点连一条长度为0的边 跑一边起点为0的spfa
对于每个点的d[i]就是到0点的最短距离

HDU 3440

题目要求

有n个屋子，超人从最矮的屋子开始，依次跳下比当前屋子高且最接近当前高度的屋子（即按照屋子高度增序来跳）,但超人跳跃还有一个水平距离限制D，他每次跳的水平距离<=D
可以水平移动屋子，使得最矮的屋子和最高的屋子的水平距离最大。如果无论怎样移动，超人都无法跳到最后那个屋子则输出-1

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define maxn 2500
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,d;
struct node{
	int h;
	int id;
}a[maxn];
bool cmp(node a,node b){
	return a.h<b.h;
}
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     
  int d[maxn];     
  int p[maxn];       
  int cnt[maxn];      
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle(int s) {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    mm(d,inf);
    d[s]=0;
    inq[s]=true;
    Q.push(s);
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&d);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i].h);
			a[i].id=i;
		}
		sp.init(maxn);
		sp.n=n;
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<n;i++) sp.AddEdge(i+1,i,-1);
		for(int i=1;i<n;i++){
			int u=a[i].id,v=a[i+1].id;
			if(u>v) swap(u,v);
			sp.AddEdge(u,v,d);
		}
		int u=a[1].id,v=a[n].id;
		if(u>v) swap(u,v);
		printf("Case %d: ",Case++);
		if(sp.negativeCycle(u)) puts("-1");
		else printf("%d\n",sp.d[v]);
	}
	return 0;
}

思路

用栈模拟spfa可以加速
id=0,stak[id++]=s,u=stak[–id]
参考博客
注意:
1.本题有源点和汇点 注意建图时i+1到i连一条-1的边 而不是i到i-1 可以避免0点的出现
2.注意本题的建图方向 规定d[大]-d[小]<=limit && >=1
3.求最大值 不等式<= spfa跑最短路
4.1和n的pos也要满足是小到大

HDU 3592

题目要求

有编号为1-n的n个人按照编号顺序排队
现在给出x对人 每对人之间的距离最大是w
再给出y对人 每对人之间的距离最小是w
现问1号和n号人之间的最大可行距离是多少
若无解输出-1 若无限多组解输出-2

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define maxn 2500
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n,x,y;
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];
  int d[maxn];
  int p[maxn];
  int cnt[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle(int s) {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    mm(d,inf);
    d[s]=0;
    inq[s]=true;
    Q.push(s);
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&x,&y);
		sp.init(maxn);
		sp.n=n;
		for(int i=1;i<=x;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			sp.AddEdge(u,v,w);
		}
		for(int i=1;i<=y;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			sp.AddEdge(v,u,-w);
		}
		for(int i=1;i<n;i++) sp.AddEdge(i+1,i,0);
		if(sp.negativeCycle(1)) puts("-1");
		else if(sp.d[n]==inf) puts("-2");
		else printf("%d\n",sp.d[n]);
	}
	return 0;
}

思路

裸的差分
最大值 不等式建<= 跑spfa最短路
注意有个隐藏条件d[i+1]-d[i]>=0 不加也能过 数据水
存在负环无解 若n点无法到达 即d[n]==inf 无限组解

HDU 3666

题目要求

给你一个n*m的矩阵，现在有一个长度为n的序列a，一个长度为m的序列b，让你把这个矩阵第i行的所有元素都乘以a[i]，把第j列的元素都除以b[j]
问存不存在这样的两个序列a,b，使得经过这些操作之后的矩阵每个元素都在[L,U]之间

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define maxn 1000
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,l,u;
struct Edge {
  int from,to;
  double dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];
  double d[maxn];
  int cnt[maxn];
  int sta[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, double dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    mm(sta,0);
    int id=0;
	for(int i=1;i<=n;i++){
    	d[i]=inf;
    	inq[i]=true;
    	sta[id++]=i;
	} 
    while(id) {
      int u=sta[--id];
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          if(!inq[e.to]) { sta[id++]=e.to; inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d%d",&n,&m,&l,&u)!=EOF){
		sp.init(maxn);
		sp.n=n+m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int x;
				scanf("%d",&x);
				sp.AddEdge(i,j+n,(double)log(x)-(double)log(l));
				sp.AddEdge(j+n,i,(double)log(u)-(double)log(x));
			}
		}
		if(sp.negativeCycle()) puts("NO");
		else puts("YES");
	}
	return 0;
}

思路

由题意得对于矩阵每个元素【设为w，处于矩阵第i行，第j列】
L <= w*a[i]/b[j] <= U
两边取对数有：
lg(L) <= lg(w)+lg(a[i])-lg(b[j]) <= lg(U)
按照最长路整理得【也可以用最短路】：
①lg(a[i])-lg(b[j]) >= lg(L)-lg(w)；②lg(b[j])-lg(a[i]) >= lg(w)-lg(U)
把a和b数组合并成一个数组s得【a有n个元素，b有m个元素，这里把b接在a数组后面】：
①s(j+n) - s(i) <= lg(w) - lg(L)
②s(i) - s(j+n) <= lg(U) - lg(w)
跑最短路和最长路都可以 本题建的<=所以跑最短路
注意：
1.本题直接用队列模拟spfa会超时
2.dist和数组d为double
3.用数组模拟队列可以卡过
4.加超级源点S向所有点连一个距离为0的边 最后跑起点为0的spfa 只需要一开始0点入队即可 可以进一步加速

本文标题:差分约束专题

文章作者:Hippopmonkey

发布时间:2017-10-12, 17:47:10

最后更新:2017-10-15, 14:40:42

原始链接:http://xuboming8.github.io/2017/10/12/差分约束专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 差分约束专题
    1. 1.1. uva 11671
    2. 1.2. uva 11478
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 1384
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 1529
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 1531
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. HDU 1534
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HDU 3440
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. HDU 3592
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
    9. 1.9. HDU 3666
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
      3. 1.9.3. 思路
|