[JSOI2015]最小表示

zhouhuanyi · 2020-02-29 20:18:13 · 题解

链接：https://www.luogu.com.cn/problem/P6134

题目描述：给定一个DAG，求最多删多条边能使任意两点的连通性不会发生改变。

题解：手玩几组数据可以发现答案就是图中去掉边(u,v)后u,v仍能连通的边的条数。然后这道题就变成了求对于每一条边，(u,v)的路径条数是否大于等于2。

我们可以发现，如果将这道题稍微弱化以下，就变成了在DAG上给定q组点对(u,v)，求u是否能到达v。我们知道这道题就是有向图可达性统计那一套，所以这道题至少要用到bitset。

判断大于2不怎么好直接做，那我们可以考虑维护两个bitset:A与B，其中A维护路径条数大于等于1的,B维护路径条数大于等于2的，更新B时与A做一下与运算就可以求出B了。

#include<iostream>
#include<bitset>
#include<queue>
using namespace std;
struct node
{
    int v,nxt;
};
node edge[100001];
int n,m,cnt,len,in[100001],head[100001];
bitset<30001>A[30001];
bitset<30001>B[30001]; 
void add(int x,int y)
{
    edge[++len].v=y;
    edge[len].nxt=head[x];
    head[x]=len;
    return;
}
void top_sort()
{
    queue<int>q;
    for (int i=1;i<=n;++i)
        if (in[i]==0)
            q.push(i);
    int top;
    while (!q.empty())
    {
        top=q.front();
        q.pop();
        for (int i=head[top];i>0;i=edge[i].nxt)
        {
            in[edge[i].v]--;
            B[edge[i].v]|=(A[edge[i].v]&A[top]);
            A[edge[i].v]|=A[top];
            if (in[edge[i].v]==0)
                q.push(edge[i].v);
        }
    }
    return;
}
int main()
{
    int x,y;
    cin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        cin>>x>>y;
        add(x,y);
        in[y]++;
    }
    for (int i=1;i<=n;++i)
        A[i][i]=1;
    top_sort();
    for (int i=1;i<=n;++i)
        for (int j=head[i];j>0;j=edge[j].nxt)
            if (B[edge[j].v][i]==1)
                cnt++;
    cout<<cnt<<endl;
    return 0; 
}