本文主要是介绍2022.7.31学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

主要内容：

1.最小瓶颈路
2.kruskal 重构树
3.差分约束系统
4.强连通分量
5.DFS树
6.kosaraju算法求SCC
7.tarjan算法求SCC
8.SAT问题

最小瓶颈路

模板：

#include<bits/stdc++.h>
#define re return
#define lowbit(x) (x&(-x))
#define dec(i,l,r) for(int i=l;i>=r;--i)
#define inc(i,l,r) for(int i=l;i<=r;++i)
const int maxn=1005,maxm=200005;
using namespace std;
template<typename T>inline void rd(T&x) {
    char c;
    bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

int n,m,q,deep[maxn],hd[maxn],fa[maxn],f[maxn][25],dis[maxn][25];

struct node {
    int fr,to,nt,val;
    bool operator<(node x)const {
        re val<x.val;
    }
} e[maxn<<1],e1[maxm];

inline int find(int x) {
    re x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void dfs(int x,int fa) {
    deep[x]=deep[fa]+1;
    for(int i=0; f[f[x][i]][i]; ++i) {
        f[x][i+1]=f[f[x][i]][i];
        dis[x][i+1]=max(dis[x][i],dis[f[x][i]][i]);
    }
    for(int i=hd[x]; i; i=e[i].nt) {
        int v=e[i].to;
        if(v!=fa) {
            f[v][0]=x;
            dis[v][0]=e[i].val;
            dfs(v,x);
        }
    }
}

inline int LCA(int x,int y) {
    int ans=0;
    if(deep[x]<deep[y])x^=y^=x^=y;
    dec(i,24,0)
    if(deep[f[x][i]]>=deep[y]) {
        ans=max(ans,dis[x][i]);
        x=f[x][i];
    }
    if(x==y)re ans;

    dec(i,24,0)
    if(f[x][i]!=f[y][i]) {
        ans=max(ans,dis[x][i]);
        ans=max(ans,dis[y][i]);
        x=f[x][i];
        y=f[y][i];
    }
    re max(ans,max(dis[x][0],dis[y][0]));
}
int main() {

    int x,y,z;
    rd(n),rd(m);
    rd(q);
    inc(i,1,m) {
        rd(x),rd(y),rd(z);
        e1[i]=(node) {
            x,y,0,z
        };
    }

    sort(e1+1,e1+m+1);

    int cnt=0,k=0;
    inc(i,1,n)fa[i]=i;
    inc(i,1,m) {
        int x=e1[i].fr,y=e1[i].to,w=e1[i].val;
        int f1=find(fa[x]),f2=find(fa[y]);
        if(f1!=f2) {
            e[++k]=(node) {
                x,y,hd[x],w
            };
            hd[x]=k;
            e[++k]=(node) {
                y,x,hd[y],w
            };
            hd[y]=k;
            ++cnt;
            fa[f1]=f2;
            if(cnt==n-1)break;
        }
    }

    inc(i,1,n)
    if(!deep[i])dfs(i,0);
    int s,t;
    inc(i,1,q) {
        rd(s),rd(t);
        if(i==27)
            x=1;
        if(find(s)!=find(t))printf("-1\n");
        else printf("%d\n",LCA(s,t));
    }
    return 0;
}

kruskal 重构树

模板：

#include<bits/stdc++.h>
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
int N = 200000;
int n,m,q;
vector<int> g[200010];
int lg2[200010];
vector<int> dep, dfn;
vector<int> stmx[200010], stmn[200010], anc[200010];
int cha[200010];
struct rec {
    int x,y,z;
} edge[500010];
bool operator<(rec a,rec b) {
    return a.z<b.z;
}
int qz[200010];
int fa[200010];
int get(int x) {
    if(fa[x]==x)return x;
    else return fa[x] = get(fa[x]);
}
int kruskal() {
    int cnt = n;
    f(i,1,2*n)fa[i]=i;
    f(i, 1, m) {
        int x = get(edge[i].x);
        int y = get(edge[i].y);
        if(x == y)continue;
        else {
            int z = ++cnt;
            g[x].push_back(z);
            g[y].push_back(z);
            g[z].push_back(x);
            g[z].push_back(y);
            fa[x]=z;
            fa[y]=z;
            qz[z] = edge[i].z;
        }
    }
    return cnt;
}
int ccnt;
void dfs(int now, int fa) {
    dfn[now] = ++ccnt;
    dep[now] = dep[fa] + 1;
    anc[now][0] = fa;
    f(i, 1, lg2[dep[now]] - 1) {
        anc[now][i] = anc[anc[now][i - 1]][i - 1];
    }
    f(i, 0, (int)g[now].size() -1 ) {
        if(g[now][i] != fa) dfs(g[now][i], now);
    }
}
int lca(int qx, int qy) {
    if(dep[qx] < dep[qy]) swap(qx, qy);
    while(dep[qx] > dep[qy]) {
        qx = anc[qx][lg2[dep[qx]-dep[qy]] - 1];
    }
    if(qx == qy) return qx;
    for(int k = lg2[dep[qx]] - 1; k >= 0; k--) {
        if(anc[qx][k] != anc[qy][k]) {
            qx = anc[qx][k];
            qy = anc[qy][k];
        }
    }
    return anc[qx][0];
}

void STmx_prework() {
    f(i, 1, n) stmx[i][0] = dfn[i];
    int mx = log(n) / log(2);
    f(j, 1, mx) {
        int mxi = n - (1 << j) + 1;
        f(i, 1, mxi) {
            stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]);
        }
    }
}
void STmn_prework() {
    f(i, 1, n) stmn[i][0] = dfn[i];
    int mx = log(n) / log(2);
    f(j, 1, mx) {
        int mxi = n - (1 << j) + 1;
        f(i, 1, mxi) {
            stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int querymx(int l, int r) {
    int mx = log(r - l + 1) / log(2);
    int ans;
    ans = max(stmx[l][mx], stmx[r - (1 << mx) + 1][mx]);
    return ans;
}
int querymn(int l, int r) {
    int mx = log(r - l + 1) / log(2);
    int ans;
    ans = min(stmn[l][mx], stmn[r - (1 << mx) + 1][mx]);
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    f(i, 1, N) lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);
    int t;
    cin >> t;
    while(t--) {

        cin>>n>>m>>q;
        f(i, 1, m) {
            int u, v;
            cin >> u >> v;
            edge[i].x = u, edge[i].y = v, edge[i].z = i;
        }
        sort(edge+1,edge+m+1);
        f(i,1,2*n)g[i].clear();
        int root = kruskal();
        n=2*n;
        cl(dep, n+10);
        cl(dfn,n+10);
        f(i,0,n+9) {
            cl(anc[i],30);
            cl(stmx[i],30);
            cl(stmn[i],30);
        }

        dfs(root, 0);
        STmx_prework();
        STmn_prework();
        f(i,1,n) cha[dfn[i]] = i;
        f(i, 1, q) {
            int l, r;
            cin >> l >> r;
            if(l == r) {
                cout << 0 << " ";
                continue;
            }
            int mx = querymx(l, r), mn = querymn(l, r);
            int lcaa = lca(cha[mx], cha[mn]);
            cout << qz[lcaa] <<" ";
        }
        cout << endl;
    }
    return 0;
}

差分约束系统

模板：

#include<bits/stdc++.h>
using namespace std;
queue<long long>p;
long long n,m,a,b,c,bj[5005],sz[5005],cs[5005],wz;
long long ans,head[5005];
struct hehe {
    long long w,cd,syg;
} lsqxx[10005];
void add(long long t,long long w,long long cd) { 
    ans++;
    lsqxx[ans].w=w;
    lsqxx[ans].cd=cd;
    lsqxx[ans].syg=head[t];
    head[t]=ans;
}
bool qg() {
    for(int i=1; i<=n; i++) {
        sz[i]=1000;
    }
    while(p.empty()==false) {
        wz=p.front();
        bj[wz]=0;
        p.pop();
        for(int i=head[wz]; i!=0; i=lsqxx[i].syg) {
            if(sz[lsqxx[i].w]>sz[wz]+lsqxx[i].cd) { 
                sz[lsqxx[i].w]=sz[wz]+lsqxx[i].cd;
                if(bj[lsqxx[i].w]==0) {
                    bj[lsqxx[i].w]=1;
                    cs[lsqxx[i].w]++;
                    if(cs[lsqxx[i].w]==n) { 
                        return false;
                    }
                    p.push(lsqxx[i].w);
                }
            }
        }
    }
    return true;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        add(0,i,0);
    }
    for(int i=0; i<m; i++) {
        cin>>a>>b>>c;
        add(b,a,c);
    }
    p.push(0);
    if(qg()==false) { 
        cout<<"NO"<<endl;
    } else {
        for(int i=1; i<=n; i++) { 
            cout<<sz[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

强连通分量

模板：

#include<bits/stdc++.h>
using namespace std;
const int N=300002;
map<string,int> a;
int ver[N],next[N],head[N];
int dfn[N],low[N],s[N],ins[N],c[N];
int tot,cnt,idx,top;
void add(int x,int y) {
    ver[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}

void tarjan(int x) {
    dfn[x]=low[x]=++idx;
    s[++top]=x;
    ins[x]=1;
    for(int i=head[x]; i; i=next[i]) {
        int y=ver[i];
        if(dfn[y]==0) {
            tarjan(y);
            low[x]=min(low[y],low[x]);
        } else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) {
        cnt++;
        while(1) {
            c[s[top]]=cnt;
            ins[s[top]]=0;
            if(s[top--]==x) break;
        }
    }
}
int main() {
    int n,m ;
    scanf("%d",&n);
    string s1,s2;
    for(int i=1; i<=n ; i++) {
        cin>>s1>>s2;
        a[s1]=i;
        a[s2]=i+n;
        add(i,i+n);
    }
    scanf("%d",&m );
    for(int i=1; i<=m ; i++) {
        cin>>s1>>s2;
        add(a[s2],a[s1]);
    }
    for(int i=1; i<=n*2; i++) {
        if(dfn[i]==0)
            tarjan(i);
    }
    for(int i=1; i<=n; i++) {
        if(c[i]==c[i+n]) puts("Unsafe");
        else puts("Safe");
    }
    return 0;
}

DFS树

模板：

不讲

kosaraju算法求SCC

模板（核心）：

inline void dfs(int k)
{
    f[k]=0;
    for (int i=0;i<a[k].size();++i)
    if (f[a[k][i]]) dfs(a[k][i]);
    s.push_back(k);
}
inline void rdfs(int k)
{
    f[k]=0;
    c[k]=tot;
    t[tot]++;
    for (int i=0;i<b[k].size();++i)
    if (f[b[k][i]]) rdfs(b[k][i]);
}

tarjan算法求SCC

模板：

#include <bits/stdc++.h>
using namespace std;
const int maxn=10010;
struct edge {
    int to;
    edge(int to_) {
        to=to_;
    }
};
vector<edge> gpe[maxn];
int dfn[maxn],low[maxn],ins[maxn],scc[maxn],size[maxn],cnt=0,sccn=0;
stack<int> s;
void tarjan(int u) {
    dfn[u]=low[u]=++cnt;
    s.push(u);
    ins[u]=1;
    for(int i=0; i<gpe[u].size(); i++) {
        int v=gpe[u][i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else if(ins[v]) {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]) {
        ins[u]=0;
        scc[u]=++sccn;
        size[sccn]=1;
        while(s.top()!=u) {
            scc[s.top()]=sccn;
            ins[s.top()]=0;
            size[sccn]+=1;
            s.pop();
        }
        s.pop();
    }
    return;
}
int n,m,oud[maxn];
int main(void) {
    scanf("%d %d",&n,&m);
    memset(low,0x3f,sizeof(low));
    memset(ins,0,sizeof(ins));
    for(int i=1; i<=m; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        gpe[u].push_back(edge(v));
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i]) {
            cnt=0;
            tarjan(i);
        }
    }
    for(int u=1; u<=n; u++) {
        for(int i=0; i<gpe[u].size(); i++) {
            int v=gpe[u][i].to;
            if(scc[u]!=scc[v]) oud[scc[u]]++;
        }
    }
    int cont=0,ans=0;
    for(int i=1; i<=sccn; i++) {
        if(oud[i]==0) {
            cont++;
            ans+=size[i];
        }
    }
    if(cont==1) {
        printf("%d",ans);
    } else {
        printf("0");
    }
    return 0;
}

SAT问题

模板：

#include<bits/stdc++.h>
#define LL long long
LL in() {
    char ch;
    LL x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
const int maxn = 2e6 + 100;
struct node {
    int to;
    node *nxt;
    node(int to = 0, node *nxt = NULL): to(to), nxt(nxt) {}
    void *operator new(size_t) {
        static node *S = NULL, *T = NULL;
        return (S == T) && (T = (S = new node[1024]) + 1024), S++;
    }
};
node *head[maxn];
bool ins[maxn];
int st[maxn], top, bel[maxn], cnt, n, m, tot;
int dfn[maxn], low[maxn];
void add(int from, int to) {
    head[from] = new node(to, head[from]);
}
void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    ins[st[++top] = x] = true;
    for(node *i = head[x]; i; i = i->nxt) {
        if(!dfn[i->to]) {
            tarjan(i->to);
            low[x] = std::min(low[x], low[i->to]);
        } else if(ins[i->to]) low[x] = std::min(low[x], dfn[i->to]);
    }
    if(dfn[x] == low[x]) {
        cnt++;
        do {
            bel[st[top]] = cnt;
            ins[st[top]] = false;
            top--;
        } while(st[top + 1] != x);
    }
}
bool judge() {
    for(int i = 1; i <= n; i++) printf("i = %d, bel = [%d,%d]\n", i, bel[i], bel[i + n]);
    for(int i = 1; i <= n; i++) if(bel[i] == bel[i + n]) return true;
    return false;
}
int main() {
    n = in(), m = in();
    int x, y, xx, yy;
    for(int i = 1; i <= m; i++) {
        x = in(), xx = in(), y = in(), yy = in();
        if(xx && yy) add(x + n, y), add(y + n, x);
        if(xx && !yy) add(x + n, y + n), add(y, x);
        if(!xx && yy) add(x, y), add(y + n, x + n);
        if(!xx && !yy) add(x, y + n), add(y, x + n);
    }
    for(int i = 1; i <= n << 1; i++) if(!dfn[i]) tarjan(i);
    if(judge())    printf("IMPOSSIBLE\n");
    else {
        printf("POSSIBLE\n");
        for(int i = 1; i <= n; i++)
            printf("%d%c", bel[i] < bel[i + n]? 1 : 0, i == n? '\n' : ' ');
    }
    return 0;
}

再见

这篇关于2022.7.31学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！