[BZOJ 2118]墨墨的等式

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求[tex]x\ge 0[/tex],所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex](忽略为0的情况,为啥取最小值待会再说),对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex],将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex],同余方程都成立。

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

我们先找出任意一个合法[tex]B[/tex](比如说0吧),然后尝试加上[tex]a_i[/tex],就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。

求出来的最短路,表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数(能加多少[tex]p[/tex],就有多少个,注意不要忽略加0个的情况),并且答案符合区间减法,最后做差分即可。

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
 
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
 
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}


[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;
}

[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;
}

[BZOJ 1715]虫洞

呜……这题现在才A

这道题就是给一个图让判断有没有负环,没什么难度

然后……我写邻接表竟然开小内存了……

尽管如此我感觉我写此题时的代码风格还是不错的,比较值得学习

代码:

/**************************************************************
    Problem: 1715
    User: danihao123
    Language: C++
    Result: Accepted
    Time:92 ms
    Memory:920 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=501,maxm=5201;
namespace Graph{
    int n;
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    inline void ClearGraph(){
        memset(first,0,sizeof(first));
        memset(next,0,sizeof(next));
        memset(to,0,sizeof(to));
        memset(dist,0,sizeof(dist));
        tot=0;
    }
    int cnt[maxn];
    bool inQueue[maxn];
    int d[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        memset(cnt,0,sizeof(cnt));
        memset(inQueue,0,sizeof(inQueue));
        for(i=1;i<=n;i++){
            d[i]=0;
            cnt[i]=1;
            inQueue[i]=true;
            Q.push(i);
        }
          
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=first[u];i;i=next[i]){
                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 true;
                    }
                }
            }
        }
        return false;
    }
};
inline int readint(){
    register char c;
    register int temp=0;
    c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        temp=temp*10+c-'0';
        c=getchar();
    }
    return temp;
}
int main(){
    register int i,m,w,u,v,d;
    int F;
    F=readint();
    while(F--){
        Graph::n=readint();
        m=readint();
        w=readint();
        Graph::ClearGraph();
        for(i=1;i<=m;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,d);
            Graph::AddEdge(v,u,d);
        }
        for(i=1;i<=w;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,-d);
        }
        if(Graph::SPFA())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}