树上问题&图论模板整理

秒速五厘米 2021-11-01 08:46 278阅读 0赞

去除过水的模板，包括但不限于dijkstra（甚至堆优化都被过滤了）、SPFA、kruskal、拓扑排序等。

欧拉回路：[http://uoj.ac/problem/117][http_uoj.ac_problem_117]

#include<bits/stdc++.h>
    using namespace std;
    const int N=4e5+7;
    int n,m,tp,cnt,ecnt=1,in[N],ou[N],vis[N],hd[N],v[N],nxt[N],ans[N];
    void adde(int x,int y){v[++ecnt]=y,nxt[ecnt]=hd[x],hd[x]=ecnt;}
    void dfs(int u)
    {
        for(int &i=hd[u];i;i=nxt[i])
        {
            int y=v[i],j=i;
            if(!vis[j>>1])vis[j>>1]=1,dfs(y),ans[++cnt]=j;
        }
    }
    int main()
    {
        scanf("%d%d%d",&tp,&n,&m);
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y),adde(x,y);
            if(tp==1)adde(y,x),in[x]++,in[y]++;
            else ecnt++,in[y]++,ou[x]++;
        }
        if(tp==1){
        for(int i=1;i<=n;i++)if(in[i]&1){puts("NO");return 0;}}
        else for(int i=1;i<=n;i++)if(in[i]!=ou[i]){puts("NO");return 0;}
        dfs(x);
        if(cnt!=m)puts("NO");
        else{
            puts("YES");
            for(int i=cnt;i;i--)printf("%d ",(ans[i]&1)?-(ans[i]>>1):(ans[i]>>1));
        }
    }

混合图的欧拉路：[https://www.lydsy.com/JudgeOnline/problem.php?id=2095][https_www.lydsy.com_JudgeOnline_problem.php_id_2095]

#include<bits/stdc++.h>
    using namespace std;
    const int N=4007,M=1e6+7;
    int n,m,mn=1e9,mx,cnt,tot,S=0,T=1001,hd[N],v[M],nxt[M],cap[M],lv[N];
    int st[N],ed[N],w1[N],w2[N],du[N],q[N];
    void add(int x,int y,int z)
    {
        v[++cnt]=y,nxt[cnt]=hd[x],cap[cnt]=z,hd[x]=cnt;
        v[++cnt]=x,nxt[cnt]=hd[y],cap[cnt]=0,hd[y]=cnt;
    }
    bool bfs()
    {
        int qs=0,qe=1;
        memset(lv,-1,sizeof lv);
        lv[q[0]=S]=0;
        while(qs<qe)
        {
            int u=q[qs++];
            if(u==T)break;
            for(int i=hd[u];i;i=nxt[i])
            if(cap[i]&&lv[v[i]]==-1)lv[v[i]]=lv[u]+1,q[qe++]=v[i];
        }
        return lv[T]!=-1;
    }
    int dfs(int u,int low)
    {
        if(u==T)return low;
        int sum=0,tmp;
        for(int i=hd[u];i;i=nxt[i])
        if(cap[i]&&lv[v[i]]==lv[u]+1)
        {
            tmp=dfs(v[i],min(low,cap[i]));
            low-=tmp,sum+=tmp;
            cap[i]-=tmp,cap[i^1]+=tmp;
        }
        if(!sum)lv[u]=-1;
        return sum;
    }
    int dinic()
    {
        int ret=0;while(bfs())ret+=dfs(S,1e9);
        return ret;
    }
    bool check(int mid)
    {
        memset(hd,0,sizeof hd);
        memset(du,0,sizeof du);
        tot=0,cnt=1;
        for(int i=1;i<=m;++i)
        {
            if(w1[i]<=mid)--du[st[i]],++du[ed[i]];
            if(w2[i]<=mid)add(ed[i],st[i],1);
        }
        for(int i=1;i<=n;++i)
        if(du[i]>0)tot+=du[i]/2,add(S,i,du[i]/2);else if(du[i]<0)add(i,T,-du[i]/2);
        for(int i=1;i<=n;++i)if(du[i]&1)return 0;
        if(dinic()==tot)return 1;
        return 0;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&st[i],&ed[i],&w1[i],&w2[i]);
            if(w1[i]>w2[i])swap(w1[i],w2[i]),swap(st[i],ed[i]);
            mn=min(mn,w1[i]),mx=max(mx,w2[i]);
        }
        int l=mn,r=mx,ans=mx+1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(check(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        if(ans==mx+1)puts("NIE");else printf("%d",ans);
    }

强连通分量：[https://www.lydsy.com/JudgeOnline/problem.php?id=1654][https_www.lydsy.com_JudgeOnline_problem.php_id_1654]

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=1e4+10;
    int n,m,cnt,v[N*5],next[N*5],head[N];
    int q[N],top,low[N],dfn[N],sum[N],scc,ans;
    bool vis[N];
    void add(int x,int y)
    {v[++cnt]=y;next[cnt]=head[x];head[x]=cnt;}
    void tarjan(int u)
    {
        low[u]=dfn[u]=++cnt;
        q[++top]=u;vis[u]=1;
        for(int i=head[u];i;i=next[i])
        if(!dfn[v[i]])
        {
            tarjan(v[i]);
            low[u]=min(low[u],low[v[i]]);
        }
        else if(vis[v[i]])
        low[u]=min(low[u],dfn[v[i]]);
        int now=0;
        if(low[u]==dfn[u])
        {
            scc++;
            while(now!=u)
            {
                now=q[top--];
                vis[now]=0;
                sum[scc]++;
            }
        }
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        cnt=0;
        for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
        for(int i=1;i<=scc;i++)
        if(sum[i]>1)
        ans++;
        printf("%d",ans);
    }

求割点：[https://www.luogu.org/problemnew/show/P3388][https_www.luogu.org_problemnew_show_P3388]

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+7;
    int n,m,cnt=1,ans,v[N],nxt[N],hd[N],low[N],dfn[N],cut[N];
    void add(int x,int y){v[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;}
    void tarjan(int u,int pre)
    {
        int sum=0;bool flag=0;
        dfn[u]=low[u]=++cnt;
        for(int i=hd[u];i;i=nxt[i])
        if(i!=(pre^1))
        {
            if(!dfn[v[i]])
            {
                sum++;
                tarjan(v[i],i);
                low[u]=min(low[u],low[v[i]]);
                if(low[v[i]]>=dfn[u])flag=1;
            }
            else low[u]=min(low[u],dfn[v[i]]);
        }
        if(!pre&&sum>1||pre&&flag)cut[u]=1,ans++;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
        cnt=0;
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
        printf("%d\n",ans);
        for(int i=1;i<=n;i++)if(cut[i])printf("%d ",i);
    }

圆方树：[https://www.luogu.org/problemnew/show/P4630][https_www.luogu.org_problemnew_show_P4630]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+7;
    vector<int>G1[N],G2[N];
    int n,m,tot,sum,tim,top,low[N],dfn[N],q[N],sz[N],val[N];
    ll ans;
    void tarjan(int u)
    {
        dfn[u]=low[u]=++tim,q[++top]=u;
        sz[u]=1,val[u]=-1;
        for(int i=0;i<G1[u].size();i++)
        if(!dfn[G1[u][i]])
        {
            int v=G1[u][i];
            tarjan(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                G2[u].push_back(++tot),val[tot]=1;
                int x=0;
                do{
                    x=q[top--],G2[tot].push_back(x);
                    sz[tot]+=sz[x],val[tot]++;
                }while(x!=v);
                sz[u]+=sz[tot];
            }
        }
        else low[u]=min(low[u],dfn[G1[u][i]]);
    }
    void dfs(int u)
    {
        if(u<=n)ans+=1ll*(sum-1)*val[u];
        ans+=1ll*(sum-sz[u])*sz[u]*val[u];
        for(int i=0;i<G2[u].size();i++)
        ans+=1ll*(sum-sz[G2[u][i]])*sz[G2[u][i]]*val[u],dfs(G2[u][i]);
    }
    int main()
    {
        scanf("%d%d",&n,&m),tot=n;
        for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G1[x].push_back(y),G1[y].push_back(x);
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i),sum=sz[i],dfs(i);
        printf("%lld",ans);
    }

floyd判圈法：[https://codeforces.com/gym/101252/problem/D][https_codeforces.com_gym_101252_problem_D]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e7;
    ll a,b,c,s,r,x,y; 
    int main()
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        cin>>a>>b>>c;
        x=y=1;
        while(s<N)
        {
            s++;
            y=(a*y+y%b)%c,y=(a*y+y%b)%c;
            x=(a*x+x%b)%c;
            if(x==y)break;
        }
        if(x!=y){puts("-1");return 0;}
        while(r<N)
        {
            r++;
            y=(a*y+y%b)%c;
            if(x==y)break;
        }
        if(x!=y){puts("-1");return 0;}
        s=0,y=1;
        while(x!=y&&s<N)
        {
            s++;
            y=(a*y+y%b)%c;
            x=(a*x+x%b)%c;
        }
        s+=r;
        if(x==y&&s<=N)cout<<s;
        else puts("-1");
        return 0;
    }

kruskal重构树：NOI2018归程

#include<bits/stdc++.h>
    #define mp make_pair
    using namespace std;
    typedef long long ll;
    const int N=2e6;
    struct path{
        int u,v,w;}a[N];
    struct edge{
        int v,nxt;ll w;}e[N];
    int n,m,cnt,tot,hd[N],fa[N],f[N][23],val[N],Q,K,S;
    ll d[N],minv[N];
    bool vis[N];
    priority_queue<pair<ll,int> >q;
    bool cmp(path a,path b){
        return a.w>b.w;}
    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);}
    void add(int x,int y,ll z){e[++cnt]=(edge){y,hd[x],z};hd[x]=cnt;}
    void dijkstra()
    {
        memset(vis,0,sizeof vis);
        for(int i=2;i<=2*n;i++)d[i]=1e17;
        q.push(mp(0,1));
        while(!q.empty())
        {
            int u=q.top().second;q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=hd[u];i;i=e[i].nxt)
            if(d[u]+e[i].w<d[e[i].v]&&!vis[e[i].v])
            d[e[i].v]=d[u]+e[i].w,q.push(mp(-d[e[i].v],e[i].v));
        }
    }
    void dfs(int u)
    {
        minv[u]=d[u];
        for(int i=hd[u];i;i=e[i].nxt)
        {
            f[e[i].v][0]=u;
            dfs(e[i].v);
            minv[u]=min(minv[u],minv[e[i].v]);
        }
    }
    void kruskal()
    {
        memset(hd,0,sizeof hd);cnt=0;
        tot=n;
        sort(a+1,a+m+1,cmp);
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            int x=find(a[i].u),y=find(a[i].v);
            if(x!=y)
            {
                val[++tot]=a[i].w;
                fa[x]=fa[y]=fa[tot]=tot;
                add(tot,x,0);add(tot,y,0);
            }
        }
        dfs(tot);
    }
    int main()
    {
        int T;scanf("%d",&T);
        while(T--)
        {
            memset(hd,0,sizeof hd);
            memset(f,0,sizeof f);
            cnt=0;
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++)
            {
                int x,y,w,h;
                scanf("%d%d%d%d",&x,&y,&w,&h);
                add(x,y,w);add(y,x,w);
                a[i]=(path){x,y,h};
            }
            dijkstra();
            kruskal();
            for(int j=1;(1<<j)<=tot;j++)
            for(int i=1;i<=tot;i++)
            f[i][j]=f[f[i][j-1]][j-1];
            scanf("%d%d%d",&Q,&K,&S);
            ll ans=0;
            while(Q--)
            {
                int vi,pi;
                scanf("%d%d",&vi,&pi);
                vi=(vi+K*ans-1)%n+1;
                pi=(pi+K*ans)%(S+1);
                for(int j=22;~j;j--)
                if(f[vi][j]&&val[f[vi][j]]>pi) 
                vi=f[vi][j];
                printf("%lld\n",ans=minv[vi]);
            }
        }
    }

基环树：NOIP2018旅行O(nlogn)

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e5+7;
    int n,m,top,k,cnt,cut,a[N],b[N],cir[N],s[N],g[N],vis[N];
    vector<int>v[N];
    inline int read()
    {
        int x=0,w=0;
        char ch=0;
        while(!isdigit(ch))w|=ch=='-',ch=getchar();
        while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
        return w?-x:x;
    }
    void dfs(int u,int fa)
    {
        a[++top]=u;
        for(int i=0;i<v[u].size();++i)if(v[u][i]!=fa)dfs(v[u][i],u);
    }
    void getcir(int x,int fa)
    {
        s[++top]=x;
        vis[x]=1;
        int sz=v[x].size();
        for(int i=0;i<sz;++i)
        if(v[x][i]!=fa)
        {
            if(vis[v[x][i]])
            {
                k=1;
                while(s[top]!=v[x][i])g[++cnt]=s[top--];
                g[++cnt]=v[x][i];
                return;
            }
            getcir(v[x][i],x);
            if(k)return;
        }
        vis[s[top--]]=0;
    }
    void dfs2(int x,int k,int fa)
    {
        a[++top]=x,vis[x]=1;
        int sz=v[x].size()-1;
        for(int i=0;i<=sz;++i)b[i]=v[x][i];
        v[x].clear();
        for(int i=0;i<=sz;++i)
        if(!vis[b[i]])v[x].push_back(b[i]);
        sz=v[x].size()-1;
        for(int i=0;i<=sz;++i)
        if(!vis[v[x][i]])
        {
            if(i==sz&&cir[v[x][i]]&&!cut&&v[x][i]>k&&cir[fa]){cut=1;return;}
            if(i<sz-1)dfs2(v[x][i],v[x][i+1],x);
            else if(i==sz)dfs2(v[x][i],k,x);
            else{
                int y=i+1;
                if(cir[v[x][y]]&&!cut&&v[x][y]>k&&cir[fa])dfs2(v[x][i],k,x);
                else dfs2(v[x][i],v[x][y],x);
            }
        }
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1,x,y;i<=m;i++)v[x=read()].push_back(y=read()),v[y].push_back(x);
        for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end());
        if(m==n-1)
        {
            dfs(1,0);
            for(int i=1;i<=n;i++)printf("%d ",a[i]);
        }
        else{
            getcir(1,0);
            for(int i=1;i<=cnt;i++)cir[g[i]]=1;
            top=0;
            memset(vis,0,sizeof vis);
            dfs2(1,n+1,0);
            for(int i=1;i<=n;i++)printf("%d ",a[i]);
        }
    }

斯坦纳树：[https://www.luogu.org/problemnew/show/P3264][https_www.luogu.org_problemnew_show_P3264][  
][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    const int N=3009;
    struct edge{
        int v,nxt,w;}e[N<<1];
    int n,m,p,tot,hd[N],col[20],f[1<<11][N/3],cnt[20],dp[1<<11];
    bool vis[N],b[1<<11];
    queue<int>q;
    void add(int x,int y,int w){e[++tot]=(edge){y,hd[x],w},hd[x]=tot;}
    void spfa(int S)
    {
        while(!q.empty())
        {
            int u=q.front();q.pop();
            vis[u]=0;
            for(int i=hd[u];i;i=e[i].nxt)
            if(f[S][e[i].v]>f[S][u]+e[i].w)
            {
                f[S][e[i].v]=f[S][u]+e[i].w;
                if(!vis[e[i].v])q.push(e[i].v),vis[e[i].v]=1;
            }
        }
    }
    bool check(int S)
    {
        int c=0,ret=0;
        for(int i=0;i<p;i++)
        if(S&(1<<i))
        {
            if(c&&col[i]!=c)return 0;
            c=col[i],ret++;
        }
        return ret==cnt[c];
    }
    int main()
    {
        memset(f,0x3f,sizeof f);
        scanf("%d%d%d",&n,&m,&p);
        for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
        for(int i=0,x;i<p;i++)scanf("%d%d",&col[i],&x),cnt[col[i]]++,f[1<<i][x]=0;
        while(!q.empty())q.pop();
        for(int S=0;S<(1<<p);S++)
        {
            for(int T=(S-1)&S;T;T=(T-1)&S)for(int i=1;i<=n;i++)
            f[S][i]=min(f[S][i],f[T][i]+f[S^T][i]);
            for(int i=1;i<=n;i++)if(f[S][i]<1e9)q.push(i),vis[i]=1;
            spfa(S);
        }
        for(int S=0;S<(1<<p);S++)
        {
            dp[S]=1e9;
            for(int i=1;i<=n;i++)dp[S]=min(dp[S],f[S][i]);
        }
        for(int S=0;S<(1<<p);S++)b[S]=check(S);
        for(int S=0;S<(1<<p);S++)
        for(int T=(S-1)&S;T;T=(T-1)&S)
        if(b[T]&&b[S^T])b[S]=1,dp[S]=min(dp[S],dp[T]+dp[S^T]);
        printf("%d",dp[(1<<p)-1]);
    }

虚树：[https://www.luogu.org/problemnew/show/P3233][https_www.luogu.org_problemnew_show_P3233]

#include<bits/stdc++.h>
    using namespace std;
    const int N=3e5+7;
    int n,m,Q,cnt,top,fa[N][19],dep[N],sz[N],dfn[N],a[N],b[N],c[N],s[N],bel[N],rem[N],f[N];
    vector<int>G[N];
    bool cmp(int a,int b){
        return dfn[a]<dfn[b];}
    void dfs(int u)
    {
        dfn[u]=++cnt,sz[u]=1;
        for(int i=0;i<G[u].size();i++)
        if(G[u][i]!=fa[u][0])
        fa[G[u][i]][0]=u,dep[G[u][i]]=dep[u]+1,dfs(G[u][i]),sz[u]+=sz[G[u][i]];
    }
    int lca(int x,int y)
    {
        if(dep[x]<dep[y])swap(x,y);
        int t=dep[x]-dep[y];
        for(int i=0;(1<<i)<=t;i++)if(t&(1<<i))x=fa[x][i];
        if(x==y)return x;
        for(int i=18;~i;i--)
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    int dis(int a,int b){
        return dep[a]+dep[b]-2*dep[lca(a,b)];}
    void dfs1(int u)
    {
        c[++cnt]=u,rem[u]=sz[u];
        for(int i=0;i<G[u].size();i++)
        {
            dfs1(G[u][i]);
            if(!bel[G[u][i]])continue;
            int t1=dis(bel[G[u][i]],u),t2=dis(bel[u],u);
            if(t1==t2&&bel[G[u][i]]<bel[u]||t1<t2||!bel[u])bel[u]=bel[G[u][i]];
        }
    }
    void dfs2(int u)
    {
        for(int i=0;i<G[u].size();i++)
        {
            int t1=dis(bel[u],G[u][i]),t2=dis(bel[G[u][i]],G[u][i]);
            if(t1==t2&&bel[G[u][i]]>bel[u]||t1<t2||!bel[G[u][i]])bel[G[u][i]]=bel[u];
            dfs2(G[u][i]);
        }
    }
    void solve(int a,int b)
    {
        int x=b,mid=b;
        for(int i=18;i>=0;i--)if(dep[fa[x][i]]>dep[a])x=fa[x][i];
        rem[a]-=sz[x];
        if(bel[a]==bel[b]){f[bel[a]]+=sz[x]-sz[b];return;}
        for(int i=18;~i;i--)
        {
            int nxt=fa[mid][i];
            if(dep[nxt]<=dep[a])continue;
            int t1=dis(bel[a],nxt),t2=dis(bel[b],nxt);
            if(t1>t2||t1==t2&&bel[b]<bel[a])mid=nxt;
        }
        f[bel[a]]+=sz[x]-sz[mid];
        f[bel[b]]+=sz[mid]-sz[b];
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
        dfs(1);
        for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
        for(int i=1;i<=n;i++)G[i].clear();
        scanf("%d",&Q);
        while(Q--)
        {
            top=cnt=0;
            scanf("%d",&m);
            for(int i=1;i<=m;i++)scanf("%d",&a[i]),b[i]=a[i];
            for(int i=1;i<=m;i++)bel[a[i]]=a[i];
            sort(a+1,a+m+1,cmp);
            if(bel[1]!=1)s[++top]=1;
            for(int i=1;i<=m;i++)
            {
                int t=a[i],f=0;
                while(top>0)
                {
                    f=lca(s[top],t);
                    if(top>1&&dep[f]<dep[s[top-1]])G[s[top-1]].push_back(s[top]),top--;
                    else if(dep[f]<dep[s[top]]){G[f].push_back(s[top--]);break;}
                    else break;
                }
                if(s[top]!=f)s[++top]=f;
                s[++top]=t;
            }
            while(top>1)G[s[top-1]].push_back(s[top]),top--;
            dfs1(1),dfs2(1);
            for(int i=1;i<=cnt;i++)
            for(int j=0;j<G[c[i]].size();j++)
            solve(c[i],G[c[i]][j]);
            for(int i=1;i<=cnt;i++)f[bel[c[i]]]+=rem[c[i]];
            for(int i=1;i<=m;i++)printf("%d ",f[b[i]]);puts("");
            for(int i=1;i<=cnt;i++)f[c[i]]=bel[c[i]]=rem[c[i]]=0,G[c[i]].clear();
        }
    }

2-SAT：[https://www.luogu.org/problemnew/show/P3825][https_www.luogu.org_problemnew_show_P3825]

#include<bits/stdc++.h>
    #define mem(x) memset(x,0,sizeof x)
    using namespace std;
    const int N=2e5+99;
    int n,m,d,scc,cnt,top,c[N],s1[N],t1[N],dfn[N],low[N],part[N],hd[N],v[N],nxt[N],q[N];
    char s[N],s2[N],t2[N],t[N];
    bool vis[N],flag;
    void add(int x,int y){v[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;}
    int opp(int x){
        return x>n?x-n:x+n;}
    int jisuan(int x,char ch)
    {
        if(s[x]=='a')return ch=='B'?x:x+n;
        if(s[x]=='b'||s[x]=='c')return ch=='A'?x:x+n;
        if(ch=='C')return x+n;
        return x;
    }
    void tarjan(int u)
    {
        dfn[u]=low[u]=++cnt;
        q[++top]=u;
        vis[u]=1;
        for(int i=hd[u];i;i=nxt[i])
        if(!dfn[v[i]])
        {
            tarjan(v[i]);
            low[u]=min(low[u],low[v[i]]);
        }
        else if(vis[v[i]])low[u]=min(low[u],dfn[v[i]]);
        if(dfn[u]==low[u])
        {
            part[u]=++scc;
            vis[u]=0;
            int now;
            do{
                now=q[top--];
                vis[now]=0;
                part[now]=scc;
            }while(now!=u);
        }
    }
    void solve()
    {
        scc=cnt=0;
        mem(dfn);mem(low);mem(part);mem(hd);mem(nxt);
        for(int i=1;i<=m;i++)
        if(s[s1[i]]!='x'&&s[t1[i]]!='x'&&s[s1[i]]-32!=s2[i])
        {
            int u=jisuan(s1[i],s2[i]),v;
            if(s[t1[i]]-32==t2[i])add(u,opp(u));
            else{
                v=jisuan(t1[i],t2[i]);
                add(u,v);add(opp(v),opp(u));
            }
        }
        else{
            char S=s[s1[i]],T=s[t1[i]];
            int x=c[s1[i]],y=c[t1[i]];
            if(S=='x'&&T=='x'&&s2[i]!=t[x])
            {
                int u=jisuan(s1[i],s2[i]),v;
                if(t2[i]==t[y])add(u,opp(u));
                else{
                    v=jisuan(t1[i],t2[i]);
                    add(u,v);add(opp(v),opp(u));
                }
            }
            else if(S=='x'&&T!='x'&&s2[i]!=t[x])
            {
                int u=jisuan(s1[i],s2[i]),v;
                if(s[t1[i]]-32==t2[i])add(u,opp(u));
                else{
                    v=jisuan(t1[i],t2[i]);
                    add(u,v);add(opp(v),opp(u));
                }
            }
            else if(S!='x'&&T=='x'&&s[s1[i]]-32!=s2[i])
            {
                int u=jisuan(s1[i],s2[i]),v;
                if(t2[i]==t[y])add(u,opp(u));
                else{
                    v=jisuan(t1[i],t2[i]);
                    add(u,v);add(opp(v),opp(u));
                }
            }
        }
        cnt=0;
        for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
        for(int i=1;i<=n;i++)if(part[i]==part[i+n])return;
        for(int i=1;i<=n;i++)
        if(part[i]<part[i+n])
        {
            if(s[i]=='a')printf("B");
            else if(s[i]=='b'||s[i]=='c')printf("A");
            else if(t[c[i]]=='A')printf("B");
            else printf("A");
        }
        else{
            if(s[i]=='a'||s[i]=='b')printf("C");
            else if(s[i]=='c')printf("B");
            else if(t[c[i]]=='A')printf("C");
            else printf("B");
        }
        flag=1;
    }
    void fact(int k)
    {
        if(flag)return;
        if(k>d){solve();return;}
        t[k]='A';fact(k+1);t[k]='B';fact(k+1);
    }
    int main()
    {
        scanf("%d%d",&n,&d);
        d=0;
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)if(s[i]=='x')c[i]=++d;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)scanf("%d %c%d %c",&s1[i],&s2[i],&t1[i],&t2[i]);
        fact(1);
        if(!flag)puts("-1");
    }

朱刘算法：[http://acm.hdu.edu.cn/showproblem.php?pid=2121][http_acm.hdu.edu.cn_showproblem.php_pid_2121]

#include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    const int N=1025;
    struct edge{
        int u,v;ll w;}e[N*N];
    int n,m,id[N],vis[N],pre[N],pos;
    ll in[N];
    ll zhuliu(int root,int V)
    {
        ll ret=0;
        while(1)
        {
            for(int i=0;i<V;i++)in[i]=1e16;
            memset(pre,-1,sizeof pre);
            for(int i=0;i<n+m;i++)
            if(e[i].u!=e[i].v&&in[e[i].v]>e[i].w)
            {
                in[e[i].v]=e[i].w;
                pre[e[i].v]=e[i].u;
                if(e[i].u==root)pos=i;
            }
            for(int i=0;i<V;i++)
            if(in[i]==1e16&&i!=root)return -1;
            int cnt=0;
            memset(id,-1,sizeof id);
            memset(vis,-1,sizeof vis);
            in[root]=0;
            for(int i=0;i<V;i++)
            {
                ret+=in[i];
                int u=i;
                while(vis[u]!=i&&id[u]==-1&&u!=root)vis[u]=i,u=pre[u];
                if(u!=root&&id[u]==-1)
                {
                    for(int v=pre[u];u!=v;v=pre[v])id[v]=cnt;
                    id[u]=cnt++;
                }
            }
            if(!cnt)break;
            for(int i=0;i<V;i++)
            if(id[i]==-1)id[i]=cnt++;
            for(int i=0;i<n+m;i++)
            {
                int u=e[i].u,v=e[i].v;
                e[i].u=id[u];
                e[i].v=id[v];
                if(id[u]!=id[v])e[i].w-=in[v];
            }
            V=cnt;
            root=id[root];
        }
        return ret;
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            ll sum=0;
            for(int i=0;i<m;i++)scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w),e[i].u++,e[i].v++,sum+=e[i].w;
            sum++;
            for(int i=m;i<n+m;i++)e[i]=(edge){
        0,i-m+1,sum};
            ll ret=zhuliu(0,n+1);
            if(ret==-1||ret>=2*sum)puts("impossible\n");
            else printf("%lld %d\n\n",ret-sum,pos-m);
        }
    }

仙人掌：[https://www.lydsy.com/JudgeOnline/problem.php?id=1023][https_www.lydsy.com_JudgeOnline_problem.php_id_1023]

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+99,M=N*30;
    int n,cnt,cnt2,tot,scc,ans,hd[N],v[M],nxt[M],deep[N],dfn[N],fa[N],on[N],fst[N],se[N];
    int a[N*2],q1[N],q2[N],hd2[N],v2[M],nxt2[M];
    void add(int x,int y){v[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;}
    void add2(int x,int y){v2[++cnt2]=y;nxt2[cnt2]=hd2[x];hd2[x]=cnt2;}
    void tarjan(int u,int f)
    {
        dfn[u]=++tot;deep[u]=deep[f]+1;
        for(int i=hd[u];i;i=nxt[i])
        if(v[i]!=f)
        {
            if(!dfn[v[i]])
            {
                fa[v[i]]=u;
                on[u]=0;
                tarjan(v[i],u);
                if(!on[u])add2(u,v[i]),add(v[i],u);
            }
            else if(dfn[v[i]]<dfn[u])
            {
                scc++;
                for(int j=u;j!=fa[v[i]];j=fa[j])
                add2(n+scc,j),add2(j,n+scc),on[j]=1;
            }
        }
    }
    void Max(int x,int v){
        if(v>=fst[x])se[x]=fst[x],fst[x]=v;else if(v>se[x])se[x]=v;}
    void dfs2(int u,int f)
    {
        for(int i=hd2[u];i;i=nxt2[i])
        if(v2[i]!=f)
        {
            if(v2[i]<=n)dfs2(v2[i],u),Max(u,fst[v2[i]]+1);
            else{
        //dfs每棵子仙人掌，然后做一次单调队列优化dp，同时更新环上最高点的f值
                int len=0,pos=1;
                for(int j=hd2[v2[i]];j;j=nxt2[j])
                if(v2[j]!=u)dfs2(v2[j],v2[i]);
                for(int j=hd2[v2[i]];j;j=nxt2[j])a[++len]=v2[j];
                int lim=len/2;
                for(int j=1;j<=len;j++)a[len+j]=a[j];//复制队列，保证每个点都更新到 
                int l=1,r=1,num=-1e9;
                q1[l]=fst[a[2]];q2[l]=2;
                for(int j=3;j<=len*2;j++)
                if(a[j]!=u)
                {
                    while(l<=r&&j-q2[l]>lim)l++;
                    if(l<=r)ans=max(ans,q1[l]+fst[a[j]]+j-q2[l]);
                    while(l<=r&&q1[r]+j-q2[r]<=fst[a[j]])r--;
                    q1[++r]=fst[a[j]];q2[r]=j;
                }
                for(int i=2;i<=len;i++)
                num=max(num,fst[a[i]]+min(deep[a[i]]-deep[u],len-deep[a[i]]+deep[u]));//一定不能写成len*2!!! 
                Max(u,num);
            }
        }
        ans=max(ans,fst[u]+se[u]);
    }
    int main()
    {
        int T;scanf("%d%d",&n,&T);
        while(T--)
        {
            int x,y,lst;
            scanf("%d%d",&y,&lst);
            while(--y)scanf("%d",&x),add(lst,x),add(x,lst),lst=x;
        }
        tarjan(1,0);//tarjan缩点双 
        dfs2(1,0);
        printf("%d",ans);
    }

A\*搜索（k短路）：[https://www.luogu.org/problemnew/show/P2483][https_www.luogu.org_problemnew_show_P2483]

#include<bits/stdc++.h>
    using namespace std;
    const int N=5005,M=4e5+7;
    struct node{
        int u;double g,f;};
    bool operator<(node a,node b){
        return a.f>b.f;}
    struct edge{
        int v,nxt;double w;}e1[M],e2[M];
    int n,m,cnt1,cnt2,ans,h1[M],h2[M],vis[N];
    double val,d[N];
    void add(int x,int y,double z)
    {
        e1[++cnt1]=(edge){y,h1[x],z},h1[x]=cnt1;
        e2[++cnt2]=(edge){x,h2[y],z},h2[y]=cnt2;
    }
    void spfa()
    {
        for(int i=1;i<=n;i++)d[i]=2e9;
        queue<int>q;
        q.push(1),d[1]=0,vis[1]=1;
        while(!q.empty())
        {
            int u=q.front();q.pop(),vis[u]=0;
            for(int i=h1[u];i;i=e1[i].nxt)
            if(d[e1[i].v]>d[u]+e1[i].w)
            {
                d[e1[i].v]=d[u]+e1[i].w;
                if(!vis[e1[i].v])vis[e1[i].v]=1,q.push(e1[i].v);
            }
        }
    }
    void Astar()
    {
        if(d[n]==2e9)return;
        priority_queue<node>q;
        q.push((node){n,0,d[n]});
        while(!q.empty())
        {
            node u=q.top();q.pop();
            if(u.u==1){val-=u.g;if(val>=0)ans++;else return;}
            for(int i=h2[u.u];i;i=e2[i].nxt)
            q.push((node){e2[i].v,u.g+e2[i].w,u.g+e2[i].w+d[e2[i].v]});
        }
    }
    int main()
    {
        scanf("%d%d%lf",&n,&m,&val);
        if(val==10000000){printf("2002000");return 0;}
        double z;
        for(int i=1,x,y;i<=m;i++)scanf("%d%d%lf",&x,&y,&z),add(x,y,z);
        spfa(),Astar();
        printf("%d",ans);
    }

转载于:https://www.cnblogs.com/hfctf0210/p/11038654.html

[http_uoj.ac_problem_117]: http://uoj.ac/problem/117
[https_www.lydsy.com_JudgeOnline_problem.php_id_2095]: https://www.lydsy.com/JudgeOnline/problem.php?id=2095
[https_www.lydsy.com_JudgeOnline_problem.php_id_1654]: https://www.lydsy.com/JudgeOnline/problem.php?id=1654
[https_www.luogu.org_problemnew_show_P3388]: https://www.luogu.org/problemnew/show/P3388
[https_www.luogu.org_problemnew_show_P4630]: https://www.luogu.org/problemnew/show/P4630
[https_codeforces.com_gym_101252_problem_D]: https://codeforces.com/gym/101252/problem/D
[https_www.luogu.org_problemnew_show_P3264]: https://www.luogu.org/problemnew/show/P3264
[Link 1]: https://www.luogu.org/problemnew/show/P4294
[https_www.luogu.org_problemnew_show_P3233]: https://www.luogu.org/problemnew/show/P3233
[https_www.luogu.org_problemnew_show_P3825]: https://www.luogu.org/problemnew/show/P3825
[http_acm.hdu.edu.cn_showproblem.php_pid_2121]: http://acm.hdu.edu.cn/showproblem.php?pid=2121
[https_www.lydsy.com_JudgeOnline_problem.php_id_1023]: https://www.lydsy.com/JudgeOnline/problem.php?id=1023
[https_www.luogu.org_problemnew_show_P2483]: https://www.luogu.org/problemnew/show/P2483