spfa&差分约束模板

Posted on | In ,

cf1131D

给出一个n*m关系表，有<>=三种关系，要求为这n+m个对象分配一个值，使得满足约束关系且最大值最小。

用差分约束，＞转化为>=x+1。=转化为>=且<=。如果y要比x至少大1，就建立边x指向y。对于这样一张图，满足所有要求其实就意味着能走的边都走（满足关系），不能满足的点就松弛（变大），类似求最长路。

bfs版spfa

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1001;
typedef pair<int,int> e;
vector<e> es[2*maxn];  //因为有01两种边权，所以要记录权值
int n,m;
bool vis[maxn*2];
int d[2*maxn];
int cnt[maxn*2];    //由于每条路最多经过v个顶点，超过就有正圈
bool spfa(int s){
    queue<int> q;
    d[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;   //有可能再次入队
        for(int i=0;i<es[u].size();i++){
            int v=es[u][i].first;
            int c=es[u][i].second;
            if(d[u]+c>d[v]){
                d[v]=d[u]+c;
                cnt[v]++;   //松弛成功就计算次数,这里跟某个博客有出入，那个人只把入队的加次数……
                if(cnt[v]>m+n)
                    return false;
                if(!vis[v]){    //如果这个点已在队里就不用再重复添加，反正上一步已经更新过了，如果后来更新的更大就直接用了
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
char s[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>(s+1);
        memset(d,-1,sizeof(d));
        for(int j=1;j<=m;j++){
            if(s[j]=='<'){
                es[i].push_back(e(j+n,1));
            }else if(s[j]=='>'){
                es[j+n].push_back(e(i,1));
            }else{
                es[i].push_back(e(j+n,0));
                es[j+n].push_back(e(i,0));
            }
        }
    }
    for(int i=1;i<=n+m;i++)
        es[0].push_back(e(i,1));
    bool ok=spfa(0);
    if(ok){
        for(int i=1;i<=n+m;i++)
            if(d[i]==-1){
                ok=0;break;
            }
    }
    if(ok){
        puts("Yes");
        for(int i=1;i<=n;i++)
            printf("%d ",d[i]);
        puts("");
        for(int i=n+1;i<=m+n;i++)
            printf("%d ",d[i]);
        puts("");
    }else{
        puts("No");
    }
    return 0;
}