2021.07.23 P3275 糖果（差分约束）

[P3275 SCOI2011]糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.为了满足更多更多约束条件，合适地选择最长路或最短路（我个憨憨，强行最短路，因此还加了负号）

题意：

k个约束条件，求满足所有约束条件并且每个点的值都大于0的每个点点权之和的最小值。

分析：

v(A,B)为从A到B的边权的值，且A点点权小于B。为了让点权之和最小，强行要求A>=B||A<=B为A==B。为了满足更多约束条件，跑最长路，记得加超级源点。

当x1时，v(A,B)=v(B,A)=0;当x2时，v(A,B)=1;当x3时，v(B,A)=0;当x4时，v(B,A)=1;当x==5时，v(A,B)=0。

代码如下：

//为了满足更多的约束条件，一定要跑最长路！！！

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=1e6+10;

const ll inf=1e18;

int n,m,cnt,head[N],vis[N],tot[N];

ll dis[N];

struct node{

	int to,next,val;

}a[N];

struct nodei{

	int pos;

	ll dis;

	bool operator <(const nodei &b)const{

			return dis<b.dis;

	}

};

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void add(int u,int v,int w){

	++cnt;

	a[cnt].to=v;

	a[cnt].next=head[u];

	a[cnt].val=w;

	head[u]=cnt;

}

int spfa(int s){

	//memset(dis,-1,sizeof(dis));

	priority_queue<nodei>q;

	q.push({s,0});

	vis[s]=tot[s]=1;

	dis[s]=0;

	while(!q.empty()){

		nodei tmp=q.top();q.pop();

		int x=tmp.pos;

		vis[x]=0;

		++tot[x];

		if(tot[x]==n)return 0;

		for(int i=head[x];i;i=a[i].next){

			int v=a[i].to;

			if(dis[v]<dis[x]+a[i].val){

				dis[v]=dis[x]+a[i].val;

				if(!vis[v]){

					vis[v]=1;

					q.push({v,dis[v]});

				}

			}

		}

	}

	return 1;

}

int main(){

	n=read();m=read();

	for(int i=1;i<=m;i++){

		int op,u,v;

		op=read();u=read();v=read();

		if(op==1)add(u,v,0),add(v,u,0);

		else if(op==2){

			if(u==v)return cout<<"-1",0;

			add(u,v,1);

		}else if(op==3)add(v,u,0);

		else if(op==4){

			if(u==v)return cout<<"-1",0;

			add(v,u,1);

		}else if(op==5)add(u,v,0);

	}

	for(int i=1;i<=n;i++)add(n+1,i,1);

	if(!spfa(n+1))return cout<<"-1",0;

	ll ans=0;

	for(int i=1;i<=n;i++)ans+=dis[i];

	cout<<ans;

	return 0;

}

巴特西

2021.07.23 P3275 糖果（差分约束）

2021.07.23 P3275 糖果（差分约束）

最新文章

热门文章