BZOJ 2330 [SCOI2011]糖果 差分约束系统

#include <cstdio> #include <cstring> #include <queue> #define N 100005 using namespace std; struct Edge { int from,to,nxt,val; Edge() {} Edge(int _from,int _to,int _nxt,int _val): from(_from),to(_to),nxt(_nxt),val(_val) {} }e[N*5]; int n,m,tot,fir[N],d[N]; void Add_Edge(int from,int to,int val) { e[++tot]=Edge(from,to,fir[from],val), fir[from]=tot; return ; } bool SPFA() { static int cnt[N]; static bool inq[N]; queue<int> q; q.push(0), inq[0]=true; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=false; for(int i=fir[x];~i;i=e[i].nxt) { if(d[e[i].to]>=d[x]+e[i].val) continue; d[e[i].to]=d[x]+e[i].val; cnt[e[i].to]=cnt[x]+1; if(cnt[e[i].to]>n+1) return false; if(!inq[e[i].to]) q.push(e[i].to), inq[e[i].to]=true; } } return true; } int main() { memset(fir,-1,sizeof fir), tot=-1; scanf("%d%d",&n,&m); for(int i=n;i;--i) Add_Edge(0,i,1); for(int i=1,mode,x,y;i<=m;++i) { scanf("%d%d%d",&mode,&x,&y); if(mode==1) Add_Edge(x,y,0), Add_Edge(y,x,0); if(mode==2) Add_Edge(x,y,1); if(mode==3) Add_Edge(y,x,0); if(mode==4) Add_Edge(y,x,1); if(mode==5) Add_Edge(x,y,0); } if(!SPFA()) { puts("-1"); return 0; } long long ans=0; for(int i=1;i<=n;++i) ans+=d[i]; printf("%lld\n",ans); return 0; }