BZOJ2330 糖果[差分约束方案+spfa?/tarjan]

以往对于差分约束理解不是太深，导致这题屡次被坑，在此记录一下细节的理解。

---

差分约束实际上就是利用了spfa的一个特性：只要有$dis_y>dis_x+w_{x,y}$就松弛，直到所有边关系都满足$dis_yle dis_x+w_{x,y}$，而这一不等式恰好可以套在差分约束问题里。差分约束要求满足前面这个玩意，把每个变量的值看做$dis_i$，建边，跑spfa最短路，使得所有边都满足关系。这个之前就已经明白了。

但是忽视了一点：注意到跑出来的最短路中$dis$即为$x$的一组合法取值，并且这组取值同时加上某个值$a$，也是满足不等式约束的。不过，这些解集构成的集合，并不是解集集合的全集（有点绕），显然在跑spfa时只是使得每个点的$dis$贴着松弛他的$dis+w$，其实这个实际取值$x$还可以更小。而如果用最长路的建边方式，$x$可以更大。两者都是等效的。在这题里面，由于要求每个数都是正整数且总和最小，并不可以使用建负权边跑最短路的方法。。。因为解出来的解集即使全部平移到正数区域，你也不知道有没有哪些数可以更小一些，哪些数不能再小了。而建正权边跑最长路，根据上述分析，每个$x$也就是$dis$必然是贴着最小的可能取值的，这样就极其简便的获取最小解。

第二个点，因为spfa理论复杂度$O(mn)$，所以想卡很容易，再加上这题由于差分约束要把所有点都加入队列，所以很容易想到如果构造一条链，连边全部反过来，$1leftarrow 2leftarrow ...leftarrow n$，显然会跑接近$n^2$次，不过数据里并没有故意卡，倒是有一个顺着正向的链的data，我这里采用直接顺着加入队列就没有问题了。但是实际上还是可以卡的？另外，有的点明显spfa被卡，但是有数据连了-1的自环，可以提前特判结束。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=1e5+7;
struct thxorz{int to,nxt,w;}G[N<<1];
int Head[N],tot,inq[N],rel[N];
int n,m;
ll ans;
inline void Addedge(int x,int y,int z){G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot,G[tot].w=z;}
queue<int> q;
ll dis[N];
#define y G[j].to
inline bool spfa(){
    for(register int i=1;i<=n;++i)q.push(i),inq[i]=1,dis[i]=1;
    while(!q.empty()){
        int x=q.front();q.pop();inq[x]=0;//dbg2(x,dis[x]);
        for(register int j=Head[x];j;j=G[j].nxt)if(MAX(dis[y],dis[x]+G[j].w)){
            rel[y]=rel[x]+1;if(rel[y]>=n)return 0;
            if(!inq[y])inq[y]=1,q.push(y);
        }
    }
    return 1;
}
#undef y
int main(){//freopen("1.in","r",stdin);//freopen("test.ans","w",stdout);
    read(n),read(m);
    for(register int i=1,opt,x,y;i<=m;++i){
        read(opt),read(x),read(y);
        if(opt==1)Addedge(x,y,0),Addedge(y,x,0);
        else if(opt==2)Addedge(x,y,1);
        else if(opt==3)Addedge(y,x,0);
        else if(opt==4)Addedge(y,x,1);
        else Addedge(x,y,0);
        if((opt==2||opt==4)&&x==y){printf("-1
");return 0;}
    }
    if(spfa()){
        for(register int i=1;i<=n;++i)ans+=dis[i];
        printf("%lld
",ans);
    }
    else puts("-1");
    return 0;
}

2019.11.01UPD：

关于正权图或者负权图的差分约束有更快的线性做法。

以最长路为例，如果图上只有正权边和零边，那么，只要看有没有环是正环，也就是说，对于每一条正边，如果他在一个SCC里，那显然就是正环了，直接判无解。否则，有环的话也只能是零环，零环意味着环上所有点值相同（因为一个被更新，所有点最长路顺着一圈都被更新），所以可以把他们缩掉，这样就变成了一张DAG，这时候就可以直接拓扑排序更新最大值了，最后每个点所在SCC的值就是他的解了。复杂度线性。当然，环上有正有负就不好整了。spfa又死了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=1e5+7;
int n,m;
ll ans;
struct thxorz{
    int head[N],nxt[N<<1],to[N<<1],from[N<<1],w[N<<1],tot;
    inline void add(int x,int y,int z){to[++tot]=y,from[tot]=x,nxt[tot]=head[x],head[x]=tot,w[tot]=z;}
}G1,G2;
int dfn[N],low[N],stk[N],instk[N],bel[N],scc,tim,top;
#define y G1.to[j]
void tarjan(int x){
    dfn[x]=low[x]=++tim,stk[++top]=x,instk[x]=1;
    for(register int j=G1.head[x];j;j=G1.nxt[j]){
        if(!dfn[y])tarjan(y),MIN(low[x],low[y]);
        else if(instk[y])MIN(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        int tmp;++scc;
        do instk[tmp=stk[top--]]=0,bel[tmp]=scc;while(tmp^x);
    }
}
#undef y
queue<int> q;
int dis[N],deg[N];
#define y G2.to[j]
inline void topo(){
    for(register int i=1;i<=scc;++i){dis[i]=1;if(!deg[i])q.push(i);}
    while(!q.empty()){
        int x=q.front();q.pop();
        for(register int j=G2.head[x];j;j=G2.nxt[j]){
            MAX(dis[y],dis[x]+G2.w[j]);
            if(!(--deg[y]))q.push(y);
        }
    }
}
#undef y
int main(){//freopen("1.in","r",stdin);//freopen("test.ans","w",stdout);
    read(n),read(m);
    for(register int i=1,opt,x,y;i<=m;++i){
        read(opt),read(x),read(y);
        if(opt==1)G1.add(x,y,0),G1.add(y,x,0);
        else if(opt==2)G1.add(x,y,1);
        else if(opt==3)G1.add(y,x,0);
        else if(opt==4)G1.add(y,x,1);
        else G1.add(x,y,0);
    }
    for(register int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    for(register int t=1;t<=G1.tot;++t){
        int x=G1.from[t],y=G1.to[t];
        if(bel[x]==bel[y]&&G1.w[t]){puts("-1");return 0;}
        else if(bel[x]^bel[y])G2.add(bel[x],bel[y],G1.w[t]),++deg[bel[y]];
    }
    topo();
    for(register int i=1;i<=n;++i)ans+=dis[bel[i]];
    printf("%lld
",ans);
    return 0;
}