BZOJ 2330 [SCOI2011]糖果 差分约束spfa版

题意：自行百度，(之前做过一道candy的升级版)。方法：差分约束解析：最近在学差分约束什么的，这道是做的第一个bz上的题，感觉还是较简单的。以下我对5种操作进行描述。

case 转换不等式 转换不等式2

如上表按照差分约束的原理加边，然后再观察上表不等式方向->为求大边，即最长路。这些边是不够的，所有人应最少为1糖果，即创出个源点到各点距离为1。后记：忘了说一嘴，据黄学长观测，数据里有一条为1~10^5的链，，如果在给源点到各点加边时，如果正着加会超时的，所以倒过来加。(cheat!);ll ;struct node{int to ;int val ;int next ;};node edge[N*5] ;int head[N] ;int hash[N] ;int d[N] ;int v[N] ;int cnt ;void init(){memset(head , -1 , sizeof(head)) ;cnt = 1 ;}void edgeadd(int from , int to , int val){edge[cnt].to = to ;edge[cnt].val = val ;edge[cnt].next = head[from] ;head[from] = cnt ++ ;}int n , k ;int spfa(){memset(d , -0x3f ,sizeof(d)) ;queue <int> q ;q.push(n+1) ;d[n+1] = 0 ;v[n+1] = 1 ;hash[n+1]=1;while(!q.empty()){int u = q.front() ;q.pop() ;v[u] = 0 ;for(int i = head[u] ; i != -1 ; i = edge[i].next){int to = edge[i].to ;if(d[u] + edge[i].val > d[to]){d[to] = d[u] + edge[i].val ;if(++hash[to] >=n) return 0 ;if(!v[to]){v[to] = 1 ;q.push(to) ;}}}}return 1 ;}int main(){scanf(“%d%d” , &n , &k) ;init() ;for(int i = 1 ; i <= k ; i++){int jd ;scanf(“%d” , &jd) ;int x , y ;scanf(“%d%d” , &x , &y) ;if(jd==1){edgeadd(x,y,0);edgeadd(y,x,0);}else if(jd==2){edgeadd(x,y,1);}else if(jd==3){edgeadd(y,x,0);}else if(jd==4){edgeadd(y,x,1);}else if(jd==5){edgeadd(x,y,0);}}for(int i = n ; i >= 1 ; i–){edgeadd(n+1 , i , 1) ;}if(spfa()){ll sum = 0 ;for(int i = 1 ; i <= n ;i++){sum += d[i] ;}printf(“%lld\n” , sum) ;}else printf(“-1\n”) ;}

没有行李，没有背包，不带电脑更不要手机，