解题：SCOI 2011 糖果

题面

能把差分约束卡死的题，因为正解并不是差分约束，然而被我用一种奇怪的姿势过去了。。。

差分约束就是相等互相连零边，不超过/不低于从不多的一方向另一方连零边，超过/低于从少的一方向另一方连最小的边权——$1$，最后跑最长路。然后你会发现你被卡T了若干个点，于是开始了优化=。=

首先有一个通用的优化：去掉超级源点，改为把每个点的距离手动赋值为$1$+入队，发现好像并不能过

然而出题人的数据造水了，只需要判断有没有小于/大于自己的即可过掉绝大部分点。。。

 #include<queue>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int p[N],noww[*N],goal[*N],val[*N];

 int vis[N],inq[N],dis[N];

 int n,k,t1,t2,t3,cnt;

 long long ans;

 queue<int> qs;

 inline int read()

 {

     int ret=;

     char ch=getchar();

     while(!isdigit(ch))

         ch=getchar();

     while(isdigit(ch))

         ret=(ret<<)+(ret<<)+(ch^),ch=getchar();

     return ret;

 }

 inline void link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 void SBData()

 {

     if((t1==||t1==)&&t2==t3)

         {printf("-1"); exit();}

 }

 int main ()

 {

     register int i;

     n=read(),k=read();

     for(i=;i<=k;i++)

     {

         t1=read(),t2=read(),t3=read();

         if(t1==) link(t2,t3,),link(t3,t2,);

         else if(t1==) link(t2,t3,);

         else if(t1==) link(t3,t2,);

         else if(t1==) link(t3,t2,);

         else link(t2,t3,); SBData();

     }

     for(i=;i<=n;i++)

         qs.push(i),dis[i]=vis[i]=,inq[i]=true;

     while(!qs.empty())

     {

         int tn=qs.front();

         qs.pop(),inq[tn]=false;

         for(i=p[tn];i;i=noww[i])

             if(dis[goal[i]]<dis[tn]+val[i])

             {

                 dis[goal[i]]=dis[tn]+val[i];

                 if(!inq[goal[i]])

                 {

                     if(++vis[goal[i]]>n) {printf("-1"); return ;}

                     qs.push(goal[i]),inq[goal[i]]=true;

                 }

             }

     }

     for(i=;i<=n;i++) ans+=dis[i];

     printf("%lld",ans);

     return ;

 }