test20230111考试总结 -2023寒图论专题

前言

赛时得分情况：

A	B	C	D	E	F	G	H	I	\(\texttt{Total}\)	\(\texttt{Rank}\)
\(100\)	\(100\)	\(10\)	\(58\)	\(54\)	\(100\)	\(300\)	\(100\)	\(0\)	\(822\)	\(2\)

考试总结完善情况：

A	B	C	D	E	F	G	H	I	\(\texttt{All}\)
√	√	✖	✖	✖	✖	✖	✖	✖	✖

A. P1993 小 K 的农场

题面

给出 \(n\) 个变量 \(A_1,A_2,\cdots,A_n\)。有 \(m\) 个约束条件，约束条件分三种：

1 x y c：\(A_x-A_y\geq c\)。
2 x y c：\(A_x-A_y\leq c\)。
3 x y：\(A_x=A_y\)。

你需要输出是否存在满足条件的自然数解。如果存在输出 \(\texttt{Yes}\) 否则输出 \(\texttt{No}\)。

\(1 \leq n,m,c \leq 5 \times 10^3\)

题解

差分约束模板题。

对于第一种，\(A_x-A_y\geq c\) 可以变形成 \(A_y-A_x\leq -c\)。连边 \((x,y,-c)\)。
对于第二种，连边 \((y,x,c)\)。
对于第三种，可以看成 \(A_x-A_y\leq0\) 且 \(A_y-A_x\leq0\)，连边 \((x,y,0)\) 和 \((y,x,0)\)。

最后建立超级源点 \(O\)，对于所有变量 \(i\) 连边 \((O,i,0)\)。跑 SPFA 判负环，如果有负环就无解，否则有解。

时间复杂度 \(O(nm)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5;

int n,m;

struct edge{
    int nxt,to,w;
} g[N<<1];
int head[N],ec;
void add(int u,int v,int w){
    g[++ec].nxt=head[u];
    g[ec].to=v;
    g[ec].w=w;
    head[u]=ec;
}

int vis[N],dis[N],cq[N];

bool spfa(int s){
    queue<int> q;
    q.push(s);
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    cq[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=g[i].nxt){
            int v=g[i].to;
            if(dis[u]+g[i].w<dis[v]){
                dis[v]=dis[u]+g[i].w;
                if(!vis[v]){
                    vis[v]=1;
                    cq[v]++;
                    if(cq[v]>=(n+1)) return false;
                    q.push(v);
                }
            }
        }
    }
    return true;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int op,a,b,c;
        cin>>op>>a>>b;
        if(op==1){
            cin>>c;
            add(a,b,-c);
        }
        else if(op==2){
            cin>>c;
            add(b,a,c);
        }
        else{
            add(a,b,0);
            add(b,a,0);
        }
    }
    for(int i=1;i<=n;i++){
        add(0,i,0);
    }
    cout<<(spfa(0)?"Yes":"No");
    return 0;
}

B. P2294 [HNOI2005]狡猾的商人

题面

有 \(n\) 个变量 \(A_1,A_2,\cdots,A_n\) 和 \(m\) 个约束条件，每个约束条件形如 \(\{s,t,v\}\)，意思是 \(\sum_{i=s}^{t}=v\)。求是否存在自然数解。

\(w\) 组数据。

\(1 \leq w \lt 100,1 \leq n \lt 100,\leq m \lt 1000\)

题解

令 \(b\) 为 \(a\) 的前缀和，则对于约束 \(\{s,t,v\}\)，可以看成 \(b_t-b_{s-1}=v\)，可以化成 \(b_t-b_{s-1}\leq v,b_{s-1}-b_t\leq (-v)\) 差分约束，连边 \((s-1,t,v),(t,s-1,-v)\)，最后跑 SPFA 判负环即可。

时间复杂度 \(O(wnm)\)。

代码

#include <bits/stdc++.h>
#define CL(x) memset(x,0,sizeof(x))
using namespace std;

const int N = 1e5;

int n,m;

struct edge{
    int nxt,to,w;
} g[N<<1];
int head[N],ec;
void add(int u,int v,int w){
    g[++ec].nxt=head[u];
    g[ec].to=v;
    g[ec].w=w;
    head[u]=ec;
}

int vis[N],dis[N],cq[N];

bool spfa(int s){
    queue<int> q;
    q.push(s);
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    cq[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=g[i].nxt){
            int v=g[i].to;
            if(dis[u]+g[i].w<dis[v]){
                dis[v]=dis[u]+g[i].w;
                if(!vis[v]){
                    vis[v]=1;
                    cq[v]++;
                    if(cq[v]>=(n+1)) return false;
                    q.push(v);
                }
            }
        }
    }
    return true;
}

signed main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>m;
        CL(g);CL(head);ec=0;CL(vis);CL(cq);CL(dis);
        while(m--){
            int u,v,w;
            cin>>u>>v>>w;
            add(u-1,v,-w);
            add(v,u-1,w);
        }
        for(int i=1;i<=n;i++){
            add((n+1),i,0);
        }
        if(!spfa(n+1)) cout<<"false";
        else cout<<"true";
        cout<<'\n';
    }
    return 0;
}