图论综合

2025年8月21日 ooliver OI

S+图论综合

A. 说谎的牛牛

枚举每一个牛作为说谎的牛是否矛盾，再差分约束建图，跑一边SPFA就可以了，代码：

#include
using namespace std;
#define int long long
const int N=105;
const int M=1005;
struct node{
	int v,w;
};
int n,q,ans;
int a[M],b[M],c[M];
int s[N],t[N],d[N];
vector g[N];
int f(int x){
	queue q;
	for(int i=1;i=n) return 0;
		t[u]=0;
		for(int i=0;i>n>>q;
	for(int i=1;i>a[i]>>b[i]>>c[i];
	for(int i=1;i

`#include
using namespace std;
#define int long long
const int N=105;
const int M=1005;
struct node{
	int v,w;
};
int n,q,ans;
int a[M],b[M],c[M];
int s[N],t[N],d[N];
vector g[N];
int f(int x){
	queueint> q;
	for(int i=1;it[i]=1,s[i]=d[i]=0,q.push(i);
	while(q.size()){
		int u=q.front();
		q.pop();
		if(s[u]>=n) return 0;
		t[u]=0;
		for(int i=0;ig[u].size();i++){
			int v=g[u][i].v,w=g[u][i].w;
			if(d[u]+wd[v]){
				d[v]=d[u]+w;
				if(!t[v]){
					t[v]=1;
					q.push(v);
					s[v]++;
				}
			}
		}
	}
	return 1;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i>a[i]>>b[i]>>c[i];
	for(int i=1;i
		for(int j=1;jg[j].clear();
		for(int j=1;j
			if(a[j]==i) g[c[j]].push_back({b[j],0});
			else g[b[j]].push_back({c[j],-1});
		}
		ans+=f(i);
	}
	cout
	return 0;
}`

B. 安慰奶牛

这道题又有点权又有边权，考虑能否一起讨论。发现最终每一条边对答案的贡献是这条边边权的两倍加上两个顶点的点权，所以根据这个跑一边最小生成树即可。注意有一个过夜点，贪心选择一个点权最小的点当作过夜点即可。代码：

#include
using namespace std;
const int N=1e5+5;
struct node{
	int v,w;
};
vector t[N];
int n,m,mn=INT_MAX,ans;
int dis[N],vis[N],c[N];
void prim(){
	dis[1]=0;
	for(int i=0;idis[j]){
				minn=dis[j];
				p=j;
			}
		}
		ans+=minn;
		for(int j=0;jt[p][j].w&&!vis[v]) dis[v]=t[p][j].w;
		}
	}
}
int main(){
	cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i>c[i],mn=min(mn,c[i]);
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		t[u].push_back({v,w*2+c[u]+c[v]});
		t[v].push_back({u,w*2+c[u]+c[v]});
	}
	prim();
	cout

`#include
using namespace std;
const int N=1e5+5;
struct node{
	int v,w;
};
vector t[N];
int n,m,mn=INT_MAX,ans;
int dis[N],vis[N],c[N];
void prim(){
	dis[1]=0;
	for(int i=0;it[1].size();i++){
		int v=t[1][i].v;
		dis[v]=min(dis[v],t[1][i].w);
	}
	int p=1;
	for(int i=1;i1;i++){
		vis[p]=1;
		int minn=0x3f3f3f3f;
		for(int j=1;j
			if(!vis[j]&&minn>dis[j]){
				minn=dis[j];
				p=j;
			}
		}
		ans+=minn;
		for(int j=0;jt[p].size();j++){
			int v=t[p][j].v;
			if(dis[v]>t[p][j].w&&!vis[v]) dis[v]=t[p][j].w;
		}
	}
}
int main(){
	cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i>c[i],mn=min(mn,c[i]);
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		t[u].push_back({v,w*2+c[u]+c[v]});
		t[v].push_back({u,w*2+c[u]+c[v]});
	}
	prim();
	cout
	return 0;
}`

D. 毕加猪

问题可以转化为找到一条从 $s$ 到 $t$ 的路径，使得该路径的总权值不超过 $- k$ 。跑Bellman-Ford即可（要判断负环）。代码：

#include
using namespace std;
const int N=1e5+5;
struct node{
	int u,v,w;
}e[N];
int n,m,k;
int dis[N];
bool f(int s,int t){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	for(int i=1;idis[e[j].u]+e[j].w) dis[e[j].v]=dis[e[j].u]+e[j].w;
	for(int i=1;idis[e[j].u]+e[j].w) dis[e[j].v]=-1e9;
	return dis[t]>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i>e[i].u>>e[i].v>>e[i].w;
		int s,t;
		cin>>s>>t;
		if(f(s,t)||f(t,s)) cout

`#include
using namespace std;
const int N=1e5+5;
struct node{
	int u,v,w;
}e[N];
int n,m,k;
int dis[N];
bool f(int s,int t){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	for(int i=1;ifor(int j=1;jif(dis[e[j].v]>dis[e[j].u]+e[j].w) dis[e[j].v]=dis[e[j].u]+e[j].w;
	for(int i=1;ifor(int j=1;jif(dis[e[j].v]>dis[e[j].u]+e[j].w) dis[e[j].v]=-1e9;
	return dis[t]
}
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i>e[i].u>>e[i].v>>e[i].w;
		int s,t;
		cin>>s>>t;
		if(f(s,t)||f(t,s)) cout"yes\n";
		else cout"no\n"; 
	}
	return 0;
}`

E. 糖果

根据性质差分约束建图，然后跑一边最短路即可。

#include
using namespace std;
const int N=1e5+5;
struct Edge{
	int v,w;
	int next;
}edge[N*10];
int head[N*3],tot;
inline void add(int u,int v,int w){
	edge[++tot].v=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot;
}
inline int read(){
	int x=0;
	bool flag=1;
	char c=getchar_unlocked();
	while(c'9'){
		if(c=='-')
			flag=0;
		c=getchar_unlocked();
	}
	while(c>='0'&&c q;
	q.push_back(0);
	vis[0]=1;
	dis[0]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v, w=edge[i].w;
			if(dis[v]dis[q.front()]) q.push_front(v);
					else q.push_back(v);
					if(++cnt[v]>n){
						cout

`#include
using namespace std;
const int N=1e5+5;
struct Edge{
	int v,w;
	int next;
}edge[N*10];
int head[N*3],tot;
inline void add(int u,int v,int w){
	edge[++tot].v=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot;
}
inline int read(){
	int x=0;
	bool flag=1;
	char c=getchar_unlocked();
	while(c'0'||c>'9'){
		if(c=='-')
			flag=0;
		c=getchar_unlocked();
	}
	while(c>='0'&&c'9'){
		x=(x1)+(x3)+c-'0';
		c=getchar_unlocked();
	}
	return (flag?x:~(x-1));
}
int dis[N],cnt[N],vis[N];
int n,m;
long long ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	n=read(),m=read();
	for(int i=1;i
		int op,u,v;
		op=read(),u=read(),v=read();
		if(op==1) add(u,v,0), add(v,u,0);
		if(op==2){
			if(u==v){
				cout"-1";
				return 0;
			} 
			add(u,v,1);
		}
		if(op==3) add(v,u,0);
		if(op==4){
			if(u==v){
				cout"-1";
				return 0;
			} 
			add(v,u,1);
		}
		if(op==5) add(u,v,0);
	}
	for(int i=n;i;i--) add(0,i,1);
	dequeint> q;
	q.push_back(0);
	vis[0]=1;
	dis[0]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v, w=edge[i].w;
			if(dis[v]dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					vis[v]=1;
					if(!q.empty()&& dis[v]>dis[q.front()]) q.push_front(v);
					else q.push_back(v);
					if(++cnt[v]>n){
						cout"-1";
						return 0;
					}
				}
			}
		}
	}
	for(int i=1;idis[i];
	cout
	return 0;
}`

I. 墨墨的等式

通过非零数字的最小值 $m n$ 构建模 $m n$ 的剩余系图，用最短路求出每个余数类的最小可表示数 $d i s [i]$ ，然后利用公式 $\sum_{i = 0}^{m n - 1} \max (0, (u - d i s [i]) / m n + 1)$ 统计区间 $[l, r]$ 内能被表示的 $b$ 的个数。代码：

#include
using namespace std;
typedef long long ll;
typedef pair P;
const int N=5e5+5;
const ll inf=1e18;
int n,a[15],x,m,mn=0x3f3f3f3f,inq[N];
ll l,r,dis[N];
vector e[N];
void spfa(){
	queue que;
	fill(dis,dis+mn,inf);
	dis[0]=0;inq[0]=1;
	que.push(0);
	while(!que.empty()){
		int u=que.front();que.pop();inq[u]=0;
		for(int i=0;idis[u]+cost){
				dis[v]=dis[u]+cost;
				if(!inq[v]){
					inq[v]=1;
					que.push(v);
				}
			}
		}
	}
}
ll query(ll u){
	ll res=0;
	for(int i=0;i>n>>l>>r;
	for(int i=1;i>x;
		if(x) a[++m]=x,mn=min(mn,x);
	}
	for(int i=0;i

`#include
using namespace std;
typedef long long ll;
typedef pairint,int> P;
const int N=5e5+5;
const ll inf=1e18;
int n,a[15],x,m,mn=0x3f3f3f3f,inq[N];
ll l,r,dis[N];
vector e[N];
void spfa(){
	queueint> que;
	fill(dis,dis+mn,inf);
	dis[0]=0;inq[0]=1;
	que.push(0);
	while(!que.empty()){
		int u=que.front();que.pop();inq[u]=0;
		for(int i=0;iint)e[u].size();i++){
			int v=e[u][i].first,cost=e[u][i].second;
			if(dis[v]>dis[u]+cost){
				dis[v]=dis[u]+cost;
				if(!inq[v]){
					inq[v]=1;
					que.push(v);
				}
			}
		}
	}
}
ll query(ll u){
	ll res=0;
	for(int i=0;i
		if(dis[i]
			res+=(u-dis[i])/mn+1;
	}
	return res;
}
int main(){
	cin>>n>>l>>r;
	for(int i=1;i
		cin>>x;
		if(x) a[++m]=x,mn=min(mn,x);
	}
	for(int i=0;i
		for(int j=1;j
			if(a[j]!=mn)
				e[i].push_back(P((i+a[j])%mn,a[j]));
	spfa();
	coutquery(r)-query(l-1);
	return 0;
}`