淘宝客的网站是怎么做的,网站开发业务规划,360免费网站建设,app官网下载一.情景导入
x1-x09 ; x2-x014 ; x3-x015 ; x2-x110 ; x3-x29;
求x3-x0的最大值#xff1b; 二.数学解法
联立式子2和5#xff0c;可得x3-x023;但式子3可得x3-x015。所以最大值为15#xff1b; 三.图论
但式子多了我们就不好解了#xff0…一.情景导入
x1-x09 ; x2-x014 ; x3-x015 ; x2-x110 ; x3-x29;
求x3-x0的最大值 二.数学解法
联立式子2和5可得x3-x023;但式子3可得x3-x015。所以最大值为15 三.图论
但式子多了我们就不好解了或者说在计算机中怎么解呢
我们可以想到不妨把式子转为图的形式。我们令x0--x1的边表示为x1-x0边权值。
则以上式子可以画图为 这边x3-x0可以为即x3-x015 也可以为即x3-x028 还可以为 :即x3-x025 所以我们取最短路径即可 四.差分约束
这个即是差分约束的模型 注意
当出现负环的情况我们可知式子是无解的所以要用spfa算法判断负环
当要求的两个点没有联通时可知这两个式子没有约束所有解都有可能 五.例题
3169 -- 布局 (poj.org) 样例输入 4 2 1
1 3 10
2 4 20
2 3 3 样例输出 27 六.参考代码 /*
4 2 1
1 3 10
2 4 20
2 3 327
*/#includebits/stdc.h
#define maxn 20005
#define maxm 1001
#define inf 0x7fffffff
using namespace std;
int cnt0;
struct Edge{int u,v,w,next;
}edge[maxn];
int head[maxm];
void add(int u,int v,int w){edge[cnt](Edge){u,v,w,head[u]}; head[u]cnt;
}
int n,x,y;
bool vis[maxm];
int in[maxm],dis[maxn]; //判断负环
//基础不会的话看我以前的博客
int spfa(int x){queueint q;for(int i1;in;i){dis[i]inf;}dis[x]0;in[x];q.push(x);while(!q.empty()){int uq.front(); q.pop();vis[u]0;for(int ihead[u];i;iedge[i].next){int vedge[i].v,wedge[i].w;if(dis[u]wdis[v]){dis[v]dis[u]w;if(!vis[v]){vis[v]1;q.push(v);in[v];if(in[v]n) return -1; //负环 }}} }if(dis[n]inf) return -2; //无限制return dis[n];
}
int main(){cinnxy;int u,v,w;for(int i1;ix;i){scanf(%d%d%d,u,v,w);add(u,v,w);}for(int i1;iy;i){scanf(%d%d%d,u,v,w);add(v,u,-w);}//是站成一条直线 for(int i1;in;i){add(i1,i,-1);}coutspfa(1); return 0;
}
