AC通道:http://www.lydsy.com/JudgeOnline/problem.php?id=2330
【題解】
建圖方法很簡單(不會的去學差分限制),然後建立一個超級源S,由S向每個點連邊,注意這裡要倒着連,否則會逾時(别問我為什麼),然後跑最長路即可。
/*************
bzoj 2330
by chty
2016.11.16
*************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 1000100
#define FILE "read"
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline ll read(){
ll x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
struct node{ll y,next,v;}e[MAXN*2];
ll n,m,ans,len,Link[MAXN],dis[MAXN],vis[MAXN],cnt[MAXN],q[MAXN*2];
void insert(ll x,ll y,ll v) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;}
void init(){
n=read(); m=read();
up(i,1,m){
ll flag=read(),x=read(),y=read();
if(flag==1) insert(x,y,0),insert(y,x,0);
if(flag==2) insert(x,y,1);
if(flag==3) insert(y,x,0);
if(flag==4) insert(y,x,1);
if(flag==5) insert(x,y,0);
if(!(flag&1)&&x==y) {puts("-1"); exit(0);}
}
down(i,n,1) insert(0,i,1);
}
void spfa(){
ll head=0,tail=1;
memset(dis,-1,sizeof(dis));
q[1]=0; vis[0]=1; dis[0]=0;
while(++head<=tail){
ll x=q[head];
for(ll i=Link[x];i;i=e[i].next){
if(dis[x]+e[i].v>dis[e[i].y]){
dis[e[i].y]=dis[x]+e[i].v;
if(!vis[e[i].y]){
vis[e[i].y]=1;
if(cnt[e[i].y]==n) {puts("-1"); exit(0);}
q[++tail]=e[i].y;
cnt[e[i].y]++;
}
}
}
vis[x]=0;
}
}
void solve(){
spfa();
up(i,1,n) ans+=dis[i];
printf("%lld\n",ans);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
init();
solve();
return 0;
}