洛谷P3275,求大佬帮忙看看!
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int maxn=1e5+1,maxm=2e5+1;
int n,m,id,id2,num,cnt,tail;
int h[maxn],nxt[maxm],e[maxm],w[maxm],dfn[maxn],low[maxn],sta[maxn],c[maxn],s[maxn],dp[maxn],du[maxn];
int h2[maxn],nxt2[maxm],e2[maxm],w2[maxm];
bool ins[maxn];
long long ans;
queue<int>q;
void add(int u,int v,int c)
{
e[id]=v;
w[id]=c;
nxt[id]=h[u];
h[u]=id++;
}
void add2(int u,int v,int c)
{
e2[id2]=v;
w2[id2]=c;
nxt2[id2]=h2[u];
h2[u]=id2++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++num;
sta[++tail]=u;
ins[u]=1;
for(int i=h[u];~i;i=nxt[i])
{
int v=e[i];
if(!dfn[i])
{
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])
{
++cnt;
int v;
do
{
v=sta[tail--];
ins[v]=0;
c[v]=cnt;
s[cnt]++;
}while(u!=v);
}
}
void topsort()
{
for(int i=1;i<=cnt;i++)
{
if(!du[i])
{
q.push(i);
dp[i]=1;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h2[u];~i;i=nxt2[i])
{
int v=e2[i];
dp[v]=max(dp[v],dp[u]+w2[i]);
if(--du[v]==0)
{
q.push(v);
}
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(h));
memset(h2,-1,sizeof(h2));
for(int i=1;i<=m;i++)
{
int t,a,b;
cin>>t>>a>>b;
if(t==1)
{
add(a,b,0);
add(b,a,0);
}
if(t==2)
{
add(a,b,1);
}
if(t==3)
{
add(b,a,0);
}
if(t==4)
{
add(b,a,1);
}
if(t==5)
{
add(a,b,0);
}
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
for(int u=1;u<=n;u++)
{
for(int i=h[u];~i;i=nxt[i])
{
int v=e[i];
if(c[u]==c[v]&&w[i]==1)
{
cout<<-1;
return 0;
}
if(c[u]!=c[v])
{
add(c[u],c[v],w[i]);
du[c[v]]++;
}
}
}
topsort();
for(int i=1;i<=cnt;i++)
{
ans+=1ll*dp[i]*s[i];
}
cout<<ans;
return 0;
}