在cf上转悠的时候莫名突然想到了差分约束。。【不要问我为什么
然后去问r_64神犇
然后就学了一下差分约束系统
然后就刷了一道板子题
差分约束系统大概就是把约束条件变成边然后跑最短/长路。。。
也还挺简单的【也真是太神了
有的时候要判断能否成立 就判断一下有没有正/负权环即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// <2330.cpp> - 02/21/16 15:07:12 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100002; int n; vector <pair<int,int> > b[MAXN]; void ins(int x,int y,int k){b[x].push_back(make_pair(y,k));} queue <int> q; bool inq[MAXN]; int dis[MAXN],times[MAXN]; bool SPFA(){ for(int i=1;i<=n;i++){dis[i]=1;q.push(i);inq[i]=1;} while(!q.empty()){ int now=q.front();q.pop();inq[now]=0; for(int i=0;i<b[now].size();i++){ int next=b[now][i].first; if(dis[now]+b[now][i].second>dis[next]){ if(++times[next]==n)return 0; dis[next]=dis[now]+b[now][i].second; if(!inq[next]){q.push(next);inq[next]=1;} } } } return 1; } int main(){ n=getint(); int k=getint(); for(int i=0;i<k;i++){ int c=getint(),x=getint(),y=getint(); if(c==1){ins(x,y,0);ins(y,x,0);} else if(c==2)ins(x,y,1); else if(c==3)ins(y,x,0); else if(c==4)ins(y,x,1); else if(c==5)ins(x,y,0); } if(!SPFA()){printf("-1");return 0;} lol ans=0; for(int i=1;i<=n;i++)ans+=dis[i]; cout<<ans; return 0; } |
泥又在刷火题