首页 > 代码库 > 约分差束 例题 ZOJ 2770 火烧连营
约分差束 例题 ZOJ 2770 火烧连营
题目来源：
ZOJ Monthly, October 2006, ZOJ2770
题目描述：
大家都知道，三国时期，蜀国刘备被吴国大都督陆逊打败了。刘备失败的原因是刘备的错误
决策。他把军队分成几十个大营，每个大营驻扎一队部队，又用树木编成栅栏，把大营连成一片，
称为连营。
让我们回到那个时代。陆逊派了很多密探，获得了他的敌人－刘备军队的信息。通过密探，
他知道刘备的军队已经分成几十个大营， 这些大营连成一片 （一字排开）， 这些大营从左到右用 1…
n 编号。第 i 个大营最多能容纳 Ci 个士兵。而且通过观察刘备军队的动静，陆逊可以估计到从第 i
个大营到第 j 个大营至少有多少士兵。最后，陆逊必须估计出刘备最少有多少士兵，这样他才知
图论算法理论、实现及应用
- 196 -
道要派多少士兵去烧刘备的大营。
输入描述：
输入文件中有多个测试数据。每个测试数据的第一行，有两个整数 n(0<n≤1000)和 m(0≤m
≤10000)。第二行，有 n 个整数 C1…Cn。接下来有 m 行，每行有 3 个整数 i, j, k(0<i≤j≤n, 0≤
k<231)，表示从第 i 个大营到第 j 个大营至少有 k 个士兵。
输出描述：
对每个测试数据，输出一个整数，占一行，为陆逊估计出刘备军队至少有多少士兵。然而，
陆逊的估计可能不是很精确，如果不能很精确地估计出来，输出"Bad Estimations"。
样例输入： 样例输出：
3 2
1000 2000 1000
1 2 1100
2 3 1300
3 1
100 200 300
2 3 600
1300
Bad Estimations
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,m; 6 struct node{ 7 int from,to,value; 8 }e[25000]; 9 int ei,c[1200],d[1200],dis[1200];// dis 最短路10 // d 阵营前缀和 c 每个阵营的最大人数11 void init()12 {13 memset(dis,0x3f,sizeof(dis));14 d[0]=0;dis[n]=0;ei=0;15 }16 bool check()17 {18 for(int i=0;i<n;i++){19 for(int j=0;j<ei;j++){20 if(dis[e[j].to]>dis[e[j].from]+e[j].value && dis[e[i].from]!=0x3f)// 松弛 21 dis[e[j].to]=dis[e[j].from]+e[j].value;22 }23 }24 for(int i=0;i<ei;i++){25 if(dis[e[i].from]+e[i].value<dis[e[i].to] && dis[e[i].from]!=0x3f)26 return false;27 }28 return true;29 }30 int main()31 {32 while(scanf("%d%d",&n,&m)!=EOF)33 {34 init();35 for(int i=1;i<=n;i++){36 scanf("%d",&c[i]);37 e[ei].from=i-1;e[ei].to=i;e[ei].value=http://www.mamicode.com/c[i];ei++;38 e[ei].from=i;e[ei].to=i-1;e[ei].value=http://www.mamicode.com/0;ei++;39 d[i]=d[i-1]+c[i];40 }41 int u,v,w;42 for(int i=0;i<m;i++){43 scanf("%d%d%d",&u,&v,&w);44 e[ei].from=v;e[ei].to=u-1;e[ei].value=http://www.mamicode.com/w*(-1);ei++;45 e[ei].from=u-1;e[ei].to=v;e[ei].value=http://www.mamicode.com/d[v]-d[u-1];ei++;46 }47 if(!check()) printf("Bad Estimations\n");48 else printf("%d\n",dis[n]-dis[0]);49 }50 return 0;51 }
思路：把各个条件处理成一个不等式（最好全是大于或者全是小于），然后构造有向图，跑一边最短路检验
约分差束 例题 ZOJ 2770 火烧连营
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。