orz orz orz
关于差分约束:用于解决一堆不等式的解。关于一堆不等式的解，要么有无数个要么无解。
eg：X1 - X2 <= 0 X1 - X5 <= -1 X2 - X5 <= 1 X3 - X1 <= 5 X4 - X1 <= 4 X4 - X3 <= -1 X5 - X3 <= -3 X5 - X4 <= -3
对于解出的一组解{x1,x2,x3,x4,x5}，可以得到{x1+k,x2+k,x3+k,x4+k,x5+k}仍然是这个不等式的解。
差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于有向图中的任何一条边<x, y>，都有： dis[y] <= dis[x] +len[x][y] 其中：dis[x]和dis[y]是从源点分别到点x和点y的最短路径的长度，len[x][y]是边<x,y>的长度值。 这是很显然的：如果存在顶点x到顶点y的有向边，那么从源点到顶点y的最短路径长度小于等于从源点到顶点x的最短路径长度加上边<x,y>的长度值。 显然以上不等式就是dis[y] - dis[x] <=len[x][y]。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图。
对于限制解的最大值，我们可以设置一个x0，使xn-x0<=0，以此连边，就可以使所有解<=x0。
对于求解最大值，我们建立边跑最短路，求解最小值，我们建边跑最长路。SPFA跑出负环则无解。
由于本题正解不是差分约束，所以以下代码不能AC
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 4e5+5;
const int inf = 0x3f3f3f3f;
int len[maxn],owo,nt[maxn],la[maxn],en[maxn];
void adg(int x,int y,int z) {
en[++owo]=y; nt[owo]=la[x]; la[x]=owo; len[owo]=z;
}
int n,k;
bool flag;
int dis[maxn];
bool rd[maxn];
int rdc[maxn];
queueq;
void spfa() {
for(int i=n;i>=1;i--) {
dis[i] = -inf;
adg(n+1,i,0);
}
dis[n+1] = 1; q.push(n+1); rd[n+1]=1;
while(q.size()) {
int x = q.front(); q.pop();
rd[x] = 0;
if((++rdc[x])==n-1) {
flag = 1; break;
}
for(int it=la[x];it;it=nt[it]) {
int y = en[it];
if(dis[y]啊除了该差分约束之外，还可以跑topsort。具体做法就是先连135的边，如果缩在同一个环里面则证明必须都相等。然后用2,4去连，如果2，4连到同一个环则无解。之后跑topsort，如果topsort有没有访问到的则证明有环，无解。
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 2e5+5;
int n,k;
struct ed{
int en; bool tr;//是否可以相等
}z[maxn];
int fr[maxn];
vectorve[maxn],vee[maxn];
int ersi;
int dfn[maxn],low[maxn],idcnt;
bool inst[maxn];
int st[maxn],sttop;
int blo[maxn],scc;
int dian[maxn];
void tarjan(int x) {
dfn[x] = low[x] = ++idcnt;
inst[x] = 1; st[++sttop] = x;
for(auto it:ve[x]) {
int y = it.en;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
} else if(inst[y]) low[x] = min(low[x],dfn[y]);
}
if(low[x]==dfn[x]) {
int y = 0;
++scc;
do{
y = st[sttop--];
inst[y] = 0;
blo[y] = scc;
dian[scc]++;
}while(y!=x);
}
}
queueq;
bool vis[maxn];
int rd[maxn],dp[maxn];
void topsort() {
for(int i=1;i<=scc;i++) {
if(!rd[i]) {
q.push(i); dp[i] = 1;
}
}
while(q.size()) {
int x = q.front(); q.pop();
vis[x] = 1;
for(auto it:vee[x]) {
int y = it.en; bool fl = it.tr;
if(fl) {
dp[y] = max(dp[y],dp[x]);
} else {
dp[y] = max(dp[y],dp[x]+1);
}
rd[y]--;
if(!rd[y]) q.push(y);
}
}
for(int i=1;i<=scc;i++) {
if(!vis[i]) {
puts("-1"); exit(0);
}
}
long long ans = 0;
for(int i=1;i<=scc;i++) {
ans += 1ll*dp[i]*dian[i];
}
printf("%lld",ans);
}
int main(){
scanf("%d%d",&n,&k);
int op,A,B;
for(int i=1;i<=k;i++) {
scanf("%d%d%d",&op,&A,&B);
if(op==1) {
ve[A].push_back((ed){B,1});
ve[B].push_back((ed){A,1});
} else if(op==2) {
z[++ersi] = (ed){B,0};
fr[ersi] = A;
} else if(op==3) {
ve[B].push_back((ed){A,1});
} else if(op==4) {
z[++ersi] = (ed){A,0};
fr[ersi] = B;
} else if(op==5) {
ve[A].push_back((ed){B,1});
}
}
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
}
for(int x=1;x<=n;x++) {
for(auto it:ve[x]) {
int y = it.en;
if(blo[x]!=blo[y]) {
vee[blo[x]].push_back((ed){blo[y],1});
rd[blo[y]]++;
}
}
}
for(int i=1;i<=ersi;i++) {
int x = blo[fr[i]];
int y = blo[z[i].en];
if(x==y) {
puts("-1");
exit(0);
} else {
vee[x].push_back((ed){y,0});
rd[y]++;
}
}
// cerr<<"yo"< B 则 B向A连边。