题目链接： https://acm.uestc.edu.cn/problem/ji-jie-jie-dai-zhao-gong-zuo/description

分析：

首先按照输入的关系建图，大小连有向边，相等连无向边。

然后超级源点连到所有的点，从超级源点跑最长路即可。

为了防止出现环，加入count数组记录一个点被访问的次数，如果超过阈值，则跳出。

一般的最长路好像都是跑负权边，但是这道题可以将传统的spfa（所有点为INF，源点为0，<）改为（所有点为0，源点为1，>）的方式跑出答案。

代码：

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
const int INF = 0x3f3f3f3f;

///////////////////////////
struct edge
{
    int from,to,cost;
};
edge es[5001];
int d[1001];
int cnt[1001];
int n,m,tot=0;
int o,a,b;
bool is=true;
void shortest_path(int s)
{
    for(int i=0;i<=n;++i)
    {
        d[i]=0;
        cnt[i]=0;
    }
    d[s]=1;
    while(true)
    {
        bool update=false;
        for(int i=0;i<tot;++i)
        {
            edge e=es[i];
            if(d[e.from] != 0 && d[e.to] < d[e.from] + e.cost)
            {
                d[e.to] = d[e.from] + e.cost;
                update=true;
                if(e.from)
                {
                    ++cnt[e.from];
                    if(cnt[e.from] > n/2)
                    {
                        is=false;
                        update=false;
                        break;
                    }
                }
            }
        }
        if(!update)
            break;
    }
}
////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        es[tot++]=edge{0,i,0};
    }
    for(int i=0;i<m;++i)
    {
        cin>>o>>a>>b;
        if(o==1)
        {
            es[tot++]=edge{b,a,1};
        }
        else if(o==2)
        {
            es[tot++]=edge{a,b,1};
        }
        else if(o==3)
        {
            es[tot++]=edge{b,a,0};
            es[tot++]=edge{a,b,0};
        }
    }
    shortest_path(0);
    if(is)
    {
        int sum=0;
        for(int i=1;i<=n;++i)
        {
            sum+=d[i];
        }
        cout<<sum<<endl;
    }
    else
    {
        cout<<-1<<endl;
    }
    return 0;
}