如何做网站免费搭桥链接,晋江论坛怎么发图,深圳公共资源交易中心官网,南京网站推广Portal.
差分约束。
发现题中每个农场的作物数 x i x_i xi 要满足以下约束关系#xff1a; { x a − x b ≥ c 1 x a − x b ≤ c 2 x a x b \begin{cases} x_a-x_b\geq c_1\\ x_a-x_b\leq c_2\\ x_ax_b \end{cases} ⎩ ⎨ ⎧xa−xb≥c1xa−xb≤c2xaxb…Portal.
差分约束。
发现题中每个农场的作物数 x i x_i xi 要满足以下约束关系 { x a − x b ≥ c 1 x a − x b ≤ c 2 x a x b \begin{cases} x_a-x_b\geq c_1\\ x_a-x_b\leq c_2\\ x_ax_b \end{cases} ⎩ ⎨ ⎧xa−xb≥c1xa−xb≤c2xaxb 把以上关系进行转化重点是“相等”这一约束关系的转化 { x a − x b ≥ c 1 x b − x a ≥ − c 2 x b − x a ≥ 0 x a − x b ≥ 0 \begin{cases} x_a-x_b\geq c_1\\ x_b-x_a\geq -c_2\\ x_b-x_a\geq 0\\ x_a-x_b\geq 0\\ \end{cases} ⎩ ⎨ ⎧xa−xb≥c1xb−xa≥−c2xb−xa≥0xa−xb≥0 按照上述约束关系SPFA 求最长路即可。注意此时 dis 要赋值为 − inf -\inf −inf。
注意若图不连通可能会出现有 x i x_i xi 值为 − inf -\inf −inf 的情况所以要建立超级源点。
#include bits/stdc.h
using namespace std;const int maxn5005,maxm1e45;
int head[maxn],cnt,tot[maxn],dis[maxn],n,m;
bool vis[maxn];
struct edge{int to,nxt,w;}e[maxm];void add(int x,int y,int z){e[cnt]{y,head[x],z},head[x]cnt;}bool spfa(int s)
{queueint q;memset(dis,-0x3f3f3f,sizeof dis);dis[s]0,q.push(s),vis[s]1,tot[s];while(!q.empty()){int xq.front();q.pop(),vis[x]0;for(int ihead[x];i;ie[i].nxt)if(dis[e[i].to]dis[x]e[i].w){dis[e[i].to]dis[x]e[i].w;if(!vis[e[i].to]) vis[e[i].to]1,q.push(e[i].to),tot[e[i].to];if(tot[e[i].to]n) return 0;}}return 1;
}int main()
{cinnm;for(int i1;im;i){int op;cinop;if(op1){int a,b,c;cinabc;add(b,a,c);}else if(op2){int a,b,c;cinabc;add(a,b,-c);}else{int a,b;cinab;add(a,b,0),add(b,a,0);}}for(int i1;in;i) add(0,i,0);if(spfa(1)) coutYes;else coutNo;return 0;
}
