记录编号	578516	评测结果	AAAAAAAAAA
题目名称	[SCOI2011] 糖果	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.110 s
提交时间	2023-03-23 15:33:30	内存使用	25.35 MiB

#include<bits/stdc++.h>
#include<vector>
#define ll long long
using namespace std;
ll read(){
    char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
ll head[200005],nxt[200005],dfn[200005],low[200005],sta[200005],vis[200005],col[200005],in[200005];
ll co,ta,cnt,n,k,top,ans;
struct node{
    ll to,val;
}L[200005];
struct edge{
    ll sum,num,in,tot;
    vector<pair<ll,ll> > go;
}f[200005];
void add(ll x,ll y,ll c){
    L[cnt]=(node){y,c};
    nxt[cnt]=head[x];head[x]=cnt;cnt++;
}
void tarjan(ll x){
    low[x]=dfn[x]=++ta;
    vis[x]=1;sta[++top]=x;
    for(ll i=head[x];i!=-1;i=nxt[i]){
        ll to=L[i].to;
        if(!dfn[to]) tarjan(to),low[x]=min(low[x],low[to]);
        else if(vis[to]) low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x]){
        co++;ll now=0;
        while(now!=x){
            now=sta[top];
            top--;
            col[now]=co;
            vis[now]=0;
            f[co].tot++;
        }
    }
}
void dfs(ll x){
    for(ll i=0;i<f[x].go.size();i++){
        ll to=f[x].go[i].first;
        ll val=f[x].go[i].second;
        if(f[x].num+val>f[to].num){
            f[to].num=f[x].num+val;
            dfs(to);
        }
    }
}
int main()
{
	freopen("tangguo.in","r",stdin);
	freopen("tangguo.out","w",stdout);
    n=read();k=read();
    memset(head,-1,sizeof(head));
    for(ll i=1;i<=k;i++){
        ll x=read(),y=read(),z=read();
        if(x==1) add(y,z,0),add(z,y,0);
        if(x==2) add(y,z,1);
        if(x==3) add(z,y,0);
        if(x==4) add(z,y,1);
        if(x==5) add(y,z,0);
    }
    for(ll i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(ll i=1;i<=n;i++)
     for(ll j=head[i];j!=-1;j=nxt[j]){
        ll to=L[j].to;
        if(col[to]==col[i]) f[col[i]].sum+=L[j].val;
        else f[col[i]].go.push_back(make_pair(col[to],L[j].val)),in[col[to]]++;         
     }
    for(ll i=1;i<=co;i++)
       if(f[i].sum>0){
        puts("-1");
        return 0;
       }
    for(ll i=1;i<=co;i++)
       if(!in[i]){
        f[i].num=1;
        dfs(i);
       }
    for(ll i=1;i<=co;i++) ans+=f[i].num*f[i].tot;
    printf("%lld",ans);
    return 0;
}