网站 建设 欢迎你,莱芜在线话题莱芜拉呱,聊城医院网站建设,哈尔滨工程信息网小 K 的农场
题目描述
小 K 在 MC 里面建立很多很多的农场#xff0c;总共 n n n 个#xff0c;以至于他自己都忘记了每个农场中种植作物的具体数量了#xff0c;他只记得一些含糊的信息#xff08;共 m m m 个#xff09;#xff0c;以下列三种形式描述#xff1a;…小 K 的农场
题目描述
小 K 在 MC 里面建立很多很多的农场总共 n n n 个以至于他自己都忘记了每个农场中种植作物的具体数量了他只记得一些含糊的信息共 m m m 个以下列三种形式描述
农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物农场 a a a 与农场 b b b 种植的作物数一样多。
但是由于小 K 的记忆有些偏差所以他想要知道存不存在一种情况使得农场的种植作物数量与他记忆中的所有信息吻合。
输入格式
第一行包括两个整数 n n n 和 m m m分别表示农场数目和小 K 记忆中的信息数目。
接下来 m m m 行
如果每行的第一个数是 1 1 1接下来有三个整数 a , b , c a,b,c a,b,c表示农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物如果每行的第一个数是 2 2 2接下来有三个整数 a , b , c a,b,c a,b,c表示农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物;如果每行的第一个数是 3 3 3接下来有两个整数 a , b a,b a,b表示农场 a a a 种植的的数量和 b b b 一样多。
输出格式
如果存在某种情况与小 K 的记忆吻合输出 Yes否则输出 No。
样例 #1
样例输入 #1
3 3
3 1 2
1 1 3 1
2 2 3 2样例输出 #1
Yes提示
对于 100 % 100\% 100% 的数据保证 1 ≤ n , m , a , b , c ≤ 5 × 1 0 3 1 \le n,m,a,b,c \le 5 \times 10^3 1≤n,m,a,b,c≤5×103。
前置芝士差分约束
大致思路
整理题意后可得 m 条信息有如下三种形式 a i − a j ≥ c a_{i}-a_{j}\ge c ai−aj≥c a i − a j ≤ c a_{i}-a_{j}\le c ai−aj≤c a i a j a_{i}a_{j} aiaj
可以将式子转化为下面的形式 a j ≤ a i − c a_{j}\le a_{i}-c aj≤ai−c a i ≤ a j c a_{i}\le a_{j}c ai≤ajc a i ≤ a j 0 a_{i}\le a_{j}0 ai≤aj0和 a j ≤ a i 0 a_{j}\le a_{i}0 aj≤ai0a
在 SPFA 中如下方式更新 dis 数组。
for(int i0;ive[x].size();i){int xvve[x][i].v,xwve[x][i].w;if(dis[xv]dis[x]xw){dis[xv]dis[x]xw;if(vis[xv]0){q.push(xv);vis[xv]1;}}
}也就是 d i s i min { d i s j j , i } dis_{i}\min\left\{dis_{j}j,i\right\} disimin{disjj,i}
于是在遇到 a i ≤ a j c a_{i}\le a_{j}c ai≤ajc
这样的不等式时我们可以从 j 到 i 建一条边权为 b 的 有向边。
为了避免图不连通的情况我们需要一个超级源点 n1与点 i 之间连一条边权为 0 的边。
那么怎么判断有没有解呢
那就是判断 负环。
那么又怎么判断负环呢
只要用一个数组来统计每个点的入队次数如果某个点的入队次数 ≥ n 1 \ge n1 ≥n1 则说明无解输出 No否则输出 Yes
AC CODE
#includebits/stdc.h
using namespace std;
const int N1e5234;
#define int long long int
int n,m,ans0,cnt0;
int dis[N],cont[N];
bool vis[N];
struct node{int v,w;
};
vectornode ve[N];
void SPFA(){memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));memset(cont,0,sizeof(cont));queueint q;dis[n1]0;vis[n1]1;cont[n1];q.push(n1);while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int i0;ive[x].size();i){int xvve[x][i].v,xwve[x][i].w;if(dis[xv]dis[x]xw){dis[xv]dis[x]xw;if(vis[xv]0){q.push(xv);cont[xv];vis[xv]1;if(cont[xv]n1){coutNoendl;return;}}}}}coutYesendl;return;
}
signed main(){node tmp;cinnm;for(int i1;im;i){int op,a,b,c;//cnt;cinopab;if(op1){//b-a-ccinc;tmp.vb,tmp.w-c;ve[a].push_back(tmp);}else if(op2){//a-bccinc;tmp.va,tmp.wc;ve[b].push_back(tmp);}else if(op3){//a-b0a-b0tmp.va;tmp.w0;ve[b].push_back(tmp);tmp.vb;ve[a].push_back(tmp);}}for(int i1;in;i){tmp.vi;tmp.w0;ve[n1].push_back(tmp);}SPFA();return 0;
}附封面
