如果你跟我一样憨憨地用了缩点+拓扑排序...
查看原帖
如果你跟我一样憨憨地用了缩点+拓扑排序...
235302
wxk123楼主2023/8/14 21:37

这方法是不对的..原因是拓扑排序时有的点的贡献会被多次统计,如1->2 2->3 1->3这个图,设答案点为3,实际上1号点的贡献会被计算两次,因此本题不能直接用拓扑排序来做。然而数据太水因此可以卡过去,但是这是不对滴... 附一个目前数据能过但是不对的代码警醒自己

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200000+15;
int n,m,sum,tim,top,s=0;
int p[maxn],head[maxn],sd[maxn],dfn[maxn],low[maxn];
int stac[maxn]; 
int h[maxn],in[maxn],dist[maxn];
struct EDGE
{
    int to;int next;int from;
}edge[maxn*10],ed[maxn*10];
void add(int x,int y)
{
    edge[++sum].next=head[x];
    edge[sum].from=x;
    edge[sum].to=y;
    head[x]=sum;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    stac[++top]=x;in[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if (!dfn[v]) {
        tarjan(v);
        low[x]=min(low[x],low[v]);
    }
        else if(in[v])
        {
            low[x]=min(low[x],dfn[v]);
        }
    }
    if (dfn[x]==low[x])
    {
        int y;
        int cnt=0;
        while (y=stac[top--])
        {
            sd[y]=x;
            in[y]=0;
            cnt++;
            if (x==y) break;
        }
        p[x]=dist[x]=cnt;
    }
}
int topo()
{
    queue <int> q;
    int tot=0;
    for (int i=1;i<=n;i++)
    if (sd[i]==i&&!in[i])
    {
        q.push(i);
     } 
    while (!q.empty())
    {
        int k=q.front();q.pop();
        for (int i=h[k];i;i=ed[i].next)
        {
            int v=ed[i].to;in[v]--;
            p[v]+=p[k];
            if (in[v]==0) q.push(v);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++){
    if(p[i]>=n&&sd[i]==i){
    	ans+=dist[i];
	}	
	}
    return ans;
}
#define mkp make_pair
map<pair<int,int>,int>mp;
signed main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
    }
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(i);
    int anss=0;
    int cnt=0;
    for (int i=1;i<=m;i++)
    {
        int x=sd[edge[i].from],y=sd[edge[i].to];

        if (x!=y&&(!mp[mkp(x,y)]))
        {
        	mp[mkp(x,y)]=1;
            ed[++s].next=h[x];
            ed[s].to=y;
            ed[s].from=x;
            h[x]=s;
            in[y]++;
        }
    }

    printf("%lld",topo());
    return 0;
}
2023/8/14 21:37
加载中...