[BZOJ 3436]小K的农场

差分约束系统的可行性问题啊……

按照要求连边然后SPFA判负环即可。

代码:

/**************************************************************
    Problem: 3436
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9224 ms
    Memory:1488 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
int n;
namespace Graph{
    int first[maxn];
    int next[maxm],to[maxm];
    ll dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,ll d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
 
    bool inQueue[maxn];
    ll d[maxn];
    int cnt[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        REP(i,n){
            inQueue[i]=true;
            Q.push(i);
        }
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            GRAPH_REP(i,u){
                if(d[to[i]]>d[u]+dist[i]){
                    d[to[i]]=d[u]+dist[i];
                    if(!inQueue[to[i]]){
                        Q.push(to[i]);
                        inQueue[to[i]]=true;
                        if(++cnt[to[i]]>n)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};
 
int main(){
    int m,opt,a,b,c;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==1){
            scanf("%d",&c);
            Graph::AddEdge(a,b,-c);
        }else{
            if(opt==2){
                scanf("%d",&c);
                Graph::AddEdge(b,a,c);
            }else{
                Graph::AddEdge(a,b,0);
                Graph::AddEdge(b,a,0);
            }
        }
    }
    if(Graph::SPFA())
        puts("Yes");
    else
        puts("No");
    return 0;
}

[BZOJ 2330]糖果

比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT

这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。

顺便说一些这题的坑点:

  1. 有一个点是一个十万个点的链。在从源点连的时候,如果正序连就会炸。倒着连就不会T。
  2. 有的点的2,4条件出现了[tex]a=b[/tex]的情况,要特判……
  3. 要开long long!

代码:

/**************************************************************
    Problem: 2330
    User: danihao123
    Language: C++
    Result: Accepted
    Time:356 ms
    Memory:7592 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
 
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
    register int i,u;
    register ll ans=0;
    queue<int> Q;
    CL_ARR(d,-1);
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        GRAPH_REP(i,u){
            if(d[u]>-1 && d[to[i]]<d[u]+dist[i]){
                d[to[i]]=d[u]+dist[i];
                if(!inQueue[to[i]]){
                    Q.push(to[i]);
                    inQueue[to[i]]=true;
                    if((++cnt[to[i]])>(n+1))
                        return -1;
                }
            }
        }
    }
    REP(i,n){
        ans+=d[i];
    }
    return ans;
}
 
int main(){
    register int i;
    int opt,u,v;
    int k;
    scanf("%d%d",&n,&k);
    REP(i,k){
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1){
            AddEdge(u,v,0);
            AddEdge(v,u,0);
        }else{
            if(opt==2){
                if(u==v){
                    puts("-1");
                    return 0;
                }
                AddEdge(u,v,1);
            }else{
                if(opt==3){
                    AddEdge(v,u,0);
                }else{
                    if(opt==4){
                        if(u==v){
                            puts("-1");
                        }
                        AddEdge(v,u,1);
                    }else{
                        AddEdge(u,v,0);
                    }
                }
            }
        }
    }
    for(i=n;i>=1;i--){
        AddEdge(0,i,1);
    }
    printf("%lld\n",SPFA());
    return 0;
}


[CodeVS 4416]FFF团卧底的后宫

差分约束又一题……也是水体……唯一难度在于两种符号。

不过这题有个坑点,无解(有负环)输出-1,答案无限大(不连通)输出-2,但……原题没说,望大家注意。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
const int maxn=1001,maxm=10002;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void Add_Edge(int u,int v,int d){
	tot++;
	next[tot]=first[u];
	first[u]=tot;
	to[tot]=v;
	dist[tot]=d;
}

int d[maxn];
int cnt[maxn];
bool inQueue[maxn];
int n;
int SPFA(){
	queue<int> Q;
	register int i,u;
	memset(d,0x7f,sizeof(d));
	d[n]=0;
	Q.push(n);
	inQueue[n]=true;
	while(!Q.empty()){
		u=Q.front();
		Q.pop();
		inQueue[u]=false;
		for(i=first[u];i;i=next[i]){
			if(d[u]<0x7f7f7f7f && d[to[i]]>d[u]+dist[i]){
				d[to[i]]=d[u]+dist[i];
				if(!inQueue[to[i]]){
					Q.push(to[i]);
					inQueue[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]>n)
					    return -1;
				}
			}
		}
	}
	if(d[1]==0x7f7f7f7f)
	    return -2;
	return d[1];
}
int main(){
	int m,k,u,v,d;
	register int i;
	scanf("%d%d%d",&n,&m,&k);
	REP(i,m){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(v,u,d);
	}
	REP(i,k){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(u,v,-d);
	}
	printf("%d\n",SPFA());
	return 0;
}

[POJ 3159]Candies

差分约束系统处女作QwQ这个题就是个裸的差分约束系统

但是粗题银啊,你粗来我们需要谈谈。

卡SPFA是怎么回事?(好像据说stack版可过)

还有,不滋磁pb_ds,又是怎么回事?

代码:

#include <cstdio>
#include <bitset>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=30001,maxm=150001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
void Add_Edge(int u,int v,int d){
	graph_cnt++;
	next[graph_cnt]=first[u];
	first[u]=graph_cnt;
	to[graph_cnt]=v;
	dist[graph_cnt]=d;
}

int n;
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef priority_queue<my_pair,vector<my_pair>,greater<my_pair> > Heap;
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    Q.push(make_pair(0,1));
	while(!Q.empty()){
		u=Q.top().second;
		Q.pop();
		if(vis[u])
			continue;
		vis[u]=true;
		for(i=first[u];i;i=next[i]){
			if(d[to[i]]>d[u]+dist[i]){
				d[to[i]]=d[u]+dist[i];
				Q.push(make_pair(d[to[i]],to[i]));
			}
		}
	}
    return d[n];
}
int main(){
	int m;
	int u,v,d;
	register int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(u,v,d);
	}
	printf("%d\n",dij());
	return 0;
}