uestc 1511 糖果 差分约束

2013.10.23 更新

    普通spfa

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int First[100005],Next[200005],W[200005],U[200005];
int cnt;
int N;
void add(int v,int u,int w)
{
    Next[cnt]=First[v];
    First[v]=cnt;
    W[cnt]=w;
    U[cnt]=u;
    cnt++;
}
int in[100005];
long long Dis[100005];
bool inq[100005];
queue<int> q;
bool spfa()
{
    int now,i,u;
    long long t;
    while(!q.empty())
    {
        now=q.front();q.pop();
        inq[now]=0;
        if(in[now]>N)return 1;
        for(i=First[now];~i;i=Next[i])
        {
            u=U[i];
            if(Dis[u]<(t=Dis[now]+W[i]))
            {
                Dis[u]=t;
                if(++in[u]>N)return 1;
                if(inq[u])continue;
                inq[u]=1;
                q.push(u);
            }
        }
    }
    return 0;
}
 inline void inp( int &n )//fast input function
{
	n=0;
	int ch=getchar_unlocked(),sign=1;
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}
	while( ch >= '0' && ch <= '9' )
 		n=(n<<3)+(n<<1)+ ch-'0', ch=getchar_unlocked();
	n=n*sign;
}

int main()
{
    int K,i,t,A,B;
    scanf("%d%d",&N,&K);
    cnt=0;
    for(i=1;i<=N;i++)
    {
        First[i]=-1;
        Dis[i]=in[i]=inq[i]=1;
        q.push(i);
    }
    for(i=0;i<K;i++)
    {
        inp(t);
        inp(A);
        inp(B);
        switch(t)
        {
            case 1:add(A,B,0);add(B,A,0);break;
            case 2:add(A,B,1);
                if(A==B)
                {
                    puts("-1");
                    return 0;
                }break;
            case 3:add(B,A,0);break;
            case 4:add(B,A,1);
                if(A==B)
                {
                    puts("-1");
                    return 0;
                }break;
            case 5:add(A,B,0);break;
        }
    }
    if(spfa())printf("%d\n",-1);
    else
    {
        long long ans=0;
        for(i=1;i<=N;i++)
        {
            ans+=Dis[i];
            //  cout<<Dis[i]<<endl;
        }
    //cout<<Min<<endl;
        printf("%lld\n",ans);
    }
}