「Luogu P1993」小K的农场 解题报告

题面

解题思路

差分约束+负环

这里只是提供板子，不做具体分析

Code

$dfs\ version:$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 10003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int to,nxt,cost;
    node(int a,int b,int c):to(a),nxt(b),cost(c){}
    node(){}
}b[N*3];
int head[N],n,m,t,d[N];
bool vis[N];
inline void add(rint x,rint y,rint cost) {
    b[++t]=node(y,head[x],cost),head[x]=t;
}
inline bool Spfa(rint k) {//dfs才是王道
    rint i,to,cost;vis[k]=1;
    for(i=head[k];i;i=b[i].nxt) {
        to=b[i].to,cost=d[k]+b[i].cost;
        if(d[to]<cost) {
            d[to]=cost;
            if(vis[to]) return 0;
            if(!Spfa(to)) return 0;
        }
    }vis[k]=0;
    return 1;
}
int main()
{
    rint i,op,x,y;
    n=read(),m=read();
    for(i=1;i<=m;i++) {
        op=read(),x=read(),y=read();
        if(op==1) add(y,x,read());
        else if(op==2) add(x,y,-read());
        else add(x,y,0),add(y,x,0);
    }
    for(i=1;i<=n;i++) add(0,i,0),d[i]=-inf;
    printf("%s",Spfa(0)?"Yes":"No");
    return 0;
}

$Spfa\ version:$

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 10003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int to,nxt,cost;
    node(int a,int b,int c):to(a),nxt(b),cost(c){}
    node(){}
}b[N<<1];
int head[N],n,m,t,usd[N],d[N];
bool vis[N],ans=1;
inline void add(rint x,rint y,rint cost) {
    b[++t]=node(y,head[x],cost),head[x]=t;
}
inline bool Spfa(rint S) {
    rint i,to,cur,cost;
    queue<int>p;
    memset(d,-inf,sizeof(d));
    d[S]=0,p.push(S),vis[S]=1;
    while(!p.empty()) {
        cur=p.front(),p.pop();vis[cur]=0;
        if(usd[cur]>n*0.3) return 0;++usd[cur];//按理说应该是大于n的，但是数据肯定不会这么恶心
        for(i=head[cur];i;i=b[i].nxt) {//一般我写的都是n*0.5，一般能过（逃
            to=b[i].to,cost=d[cur]+b[i].cost;
            if(d[to]<cost) {
                d[to]=cost;
                if(!vis[to])
                    vis[to]=1,
                    p.push(to);
            }
        }
    }return 1;
}
int main()
{
    rint i,op,x,y;
    n=read(),m=read();
    for(i=1;i<=m;i++) {
        op=read(),x=read(),y=read();
        if(op==1) add(y,x,read());
        else if(op==2) add(x,y,-read());
        else add(x,y,0),add(y,x,0);
    }
    for(i=1;i<=n&&ans;i++)
        if(!usd[i])    ans&=Spfa(i);
    printf("%s",ans?"Yes":"No");
    return 0;
}

顺便贴上 Luogu P3385 【模板】负环 的代码

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define M 3010
#define N 2010
using namespace std;
struct node{
    int to,cost;
    int nxt;
    node(int a,int b):to(a),cost(b){    }
    node(){    }
}b[M<<1];
int head[N],d[N],Ti[N];
int n,m,T,t,Min;
bool vis[N];
int read(){
    int s=0,p=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            p=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s*p;
}
void init(){
    t=0;memset(head,0,sizeof(head));
    memset(Ti,0,sizeof(Ti));Min=0;
}
void add(int x,int y,int cost){
    b[++t]=node(y,cost);b[t].nxt=head[x];head[x]=t;
}
bool SPFA()
{
    int i,cur,to,cost;
    deque<int>p;
    memset(d,INF,sizeof(d));
    memset(vis,0,sizeof(vis));
    p.push_back(1);vis[1]=1;Ti[1]=1;d[1]=0;
    while(!p.empty())
    {
        cur=p.front();p.pop_front();
        vis[cur]=0;
        if(Ti[cur]>=n||d[cur]<Min)
            return 1;
        for(i=head[cur];i;i=b[i].nxt)
        {
            to=b[i].to;cost=d[cur]+b[i].cost;
            if(d[to]>cost)
            {
                d[to]=cost;
                Ti[to]++;
                if(Ti[to]>=n||d[to]<Min)
                    return 1;
                if(!vis[to])
                {
                    vis[to]=1;
                    if(b[i].cost<0)
                        p.push_front(to);
                    else
                        p.push_back(to);
                }
            }
        }
    }
    return 0;
}
int main()
{
    int i;
    int x,y,cost;
    T=read();
    while(T--)
    {
        n=read()/2;m=read();init();
        for(i=1;i<=m;i++)
        {
            x=read();y=read();cost=read();
            Min=min(Min,cost);
            if(cost>=0)
                add(y,x,cost);
            else
                Min+=cost;
            add(x,y,cost);
        }
        if(SPFA())
            printf("YE5\n");
        else
            printf("N0\n");
    }
    return 0;
}

再贴上 Luogu P3275 [SCOI2011]糖果 的代码

#include<bits/stdc++.h>
#define rgt register
#define LL long long
#define N 100003
#define M 300003
using namespace std;
struct Edge{
    int to,nxt,cost;
    Edge(int a,int b,int c):to(a),nxt(b),cost(c){}
    Edge(){}
}b[M];
int head[N],n,T,t,d[N],usd[N];
LL ans;
bool vis[N];
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rgt int x,rgt int y,rgt int cost) {
    b[++t]=Edge(y,head[x],cost),head[x]=t;
}
inline void Spfa() {
    rgt int i,cur,to,cost;
    queue<int>p;p.push(0),vis[0]=1;
    while(!p.empty()) {
        cur=p.front(),p.pop(),vis[cur]=0;
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to,cost=b[i].cost+d[cur];
            if(d[to]<cost) {
                d[to]=cost;
                if(!vis[to]) {
                    ++usd[to];
                    if(usd[to]>n-1) {ans=-1;return;}
                    vis[to]=1;
                    p.push(to);
                }
            }
        }
    }
    for(i=1;i<=n;i++) ans+=d[i];
}
int main()
{
    int i,op,x,y;
    n=read(),T=read();
    for(i=n;i;i--) add(0,i,1);
    while(T--) {
        op=read(),x=read(),y=read();
        if(op==5) add(x,y,0);
        else if(op==2) {
            if(x==y) {printf("-1");return 0;}
            add(x,y,1);
        }
        else if(op==3) add(y,x,0);
        else if(op==4) {
            if(x==y) {printf("-1");return 0;}
            add(y,x,1);
        }
        else add(x,y,0),add(y,x,0);
    }Spfa();
    printf("%lld",ans);
    return 0;
}

貌似我还是比较喜欢已经死了的Spfa