NFLS-DAY 5

Posted on By 张, 高畅 NFLS-DAY 5无评论

T0

每日一图.jpg

明天就放假了~

T1

给定一个有n个点，m条边的有向图，求最少添加多少条边，使得图变成强连通，即任意两个点都能相互抵达。

板子，tarjan，缩点后记录出度入度，统计出度为0与入度为0的点数，两者取最大

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,in_stk[N];
int id[N],scc_cnt,Size[N];
int out[N],in[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stk[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y=stk[top--];
            in_stk[y]=0;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }
        while(y!=u);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    if(scc_cnt==1)puts("0");
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=h[i];~j;j=ne[j])
            {
                int k=e[j];
                if(id[i]!=id[k])
                {
                    out[id[i]]++; 
                    in[id[k]]++;
                }
            }
        }
        int none_out_cnt=0,none_in_cnt=0;
        for(int i=1;i<=scc_cnt;i++)
        {
            if(!in[i])none_in_cnt++;
            if(!out[i])none_out_cnt++;
        }
        printf("%d",max(none_in_cnt,none_out_cnt));
    }
    return 0;
}

T2

给一个有向图，然后选一条路径起点终点都为1的路径出来，有一次机会可以沿某条边逆方向走，问最多有多少个点可以被经过？（一个点在路径中无论出现多少正整数次对答案的贡献均为1）

感谢CZY DALAO提供的指导。
缩点后枚举每一条边作为反向边，用SPFA算出答案，统计答案。
有许许多多奇奇怪怪的细节，比如SPFA的dist初始值是-0x3f而非0

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,res;
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,in_stk[N];
int id[N],scc_cnt,distz[N],distf[N],st[N],Size[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
vector<int>Gz[N],Gf[N];
void spfaz(int S)
{
    memset(distz,-0x3f,sizeof distz);
    memset(st,0,sizeof st);
    distz[S]=0;
    queue<int>q;
    q.push(S);
    st[S]=1;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=0;i<Gz[t].size();i++)
        {
            int j=Gz[t][i];
            if(distz[j]<distz[t]+Size[j])
            {
                distz[j]=distz[t]+Size[j];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
void spfaf(int S)
{
    memset(distf,-0x3f,sizeof distf);
    memset(st,0,sizeof st);
    distf[S]=0;
    queue<int>q;
    q.push(S);
    st[S]=1;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=0;i<Gf[t].size();i++)
        {
            int j=Gf[t][i];
            if(distf[j]<distf[t]+Size[j])
            {
                distf[j]=distf[t]+Size[j];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y=stk[top--];
            in_stk[y]=0;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }
        while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            if(id[i]!=id[k])
            {
                Gz[id[i]].push_back(id[k]);
                Gf[id[k]].push_back(id[i]);
            }
        }
    }
    spfaz(id[1]);
    spfaf(id[1]);
    for(int i=1;i<=scc_cnt;i++)
    {
        for(int j=0;j<Gz[i].size();j++)
        {
            int k=Gz[i][j];
            res=max(res,distz[k]+distf[i]+Size[id[1]]);
        }
    }
    printf("%d",res);
    return 0;
}

T3

LUOGU链接

缩点后见图跑SPFA最长路（其实就是上面一题代码抄下来改一改）

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define x first
#define y second
typedef pair<int,int> PII;
int n,m,S,P,q[N],bar[N];
int h[N],e[N<<1],ne[N<<1],w[N<<1],idx;
int dfn[N],low[N],timestamp;
int id[N],scc_cnt,sum[N],dist[N],st[N];
PII edge[N<<1];
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}
int stk[N],top;
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(st[j])low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y=stk[top--];
            st[y]=0;
            id[y]=scc_cnt;
            sum[scc_cnt]+=q[y];
        }
        while(y!=u);
    }
}
queue<int>Q;
void spfa()
{
    Q.push(id[S]);
    st[id[S]]=1;
    dist[id[S]]=sum[id[S]];
    while(Q.size())
    {
        int u=Q.front();
        Q.pop();
        st[u]=0;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                if(!st[j])
                {
                    Q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    idx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&edge[i].x,&edge[i].y);
        add(edge[i].x,edge[i].y,0);
    }
    for(int i=1;i<=n;i++)scanf("%d",&q[i]);
    scanf("%d%d",&S,&P);
    for(int i=1;i<=P;i++)scanf("%d",&bar[i]);
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=m;i++)
    {
        if(id[edge[i].x]!=id[edge[i].y])add(id[edge[i].x],id[edge[i].y],sum[id[edge[i].y]]);
    }
    spfa();
    int res=0;
    for(int i=1;i<=P;i++)res=max(res,dist[id[bar[i]]]);
    printf("%d",res);
    return 0;
}

T4

给定一个有N个点，M条边的无向图，求最少添加多少条边，使得图变成边双连通，满足删除任意一条边之后，任意两个点仍然连通，即图中没有桥。

边双联通分量模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int h[N],e[N<<1],ne[N<<1],idx;
int dfn[N],low[N],timestamp,stk[N],top;
int id[N],dcc_cnt,is_bridge[N<<1],d[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<low[j])is_bridge[i]=is_bridge[i^1]=1;
        }
        else if(i!=(from^1))low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do 
        {
            y=stk[top--];
            id[y]=dcc_cnt;
        }
        while(y!=u);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++)
    {
        if(is_bridge[i])d[id[e[i]]]++;   
    }
    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
    {
        if(d[i]==1)cnt++;
    }
    printf("%d\n",(cnt+1)/2);
    return 0;
}

T5

现代社会，路是必不可少的。任意两个城镇都有路相连，而且往往不止一条。但有些路连年被各种堵塞，走着很不爽。按理说条条大路通罗马，大不了绕行其他路呗——可小C却发现：从a城到b城不管怎么走，总有一些逃不掉的必经之路。
他想请你计算一下，a到b的所有路径中，有几条路是逃不掉的？

边双后，用BFS初始化，倍增求LCA。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=8e5+5;
int n,m;
int h[N],hs[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,id[N],dcc_cnt,d[N];
int fa[N][18];
void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
        }
        else if(i!=(from^1))low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do 
        {
            y=stk[top--];
            id[y]=dcc_cnt;
        }
        while(y!=u);
    }
}
void bfs()
{
    queue<int>q;
    q.push(1);
    d[1]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=hs[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j])continue;
            d[j]=d[u]+1;
            fa[j][0]=u;
            for(int k=1;k<=17;k++)fa[j][k]=fa[fa[j][k-1]][k-1];
            q.push(j);
        }
    }
}
int LCA(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int k=17;~k;k--)
    {
        if(d[fa[a][k]]>=d[b])a=fa[a][k];
    }
    if(a==b)return a;
    for(int k=17;~k;k--)
    {
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int main()
{
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b);
        add(h,b,a);
    }
    tarjan(1,-1);
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b)
            {
                add(hs,a,b);
                add(hs,b,a);
            }
        }
    }
    bfs();
    int k;
    scanf("%d",&k);
    while(k--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a=id[a];
        b=id[b];
        int p=LCA(a,b);
        printf("%d\n",d[a]+d[b]-2*d[p]);
    }
    return 0;
}
训练日志

发表回复