题目:
Sample Input
2
2 3 4 2
96 97 199 62
Sample Output
2 2
9859 62
题意:
有三个杯子它们的容量分别是a,b,c, 并且初始状态下第一个和第二个是空的, 第三个杯子是满水的。可以把一个杯子的水倒入另一个杯子,当然,当被倒的杯子满了或者倒的杯子水完了,就不能继续倒了。
你的任务是写一个程序计算出用最少的倒水量,使得其中一个杯子里有d升水。如果不能倒出d升水的话,那么找到一个d' < d ,使得d' 最接近d。
分析:
可以把每个状态即3个水杯里的水的数量的状态看成一个点,两个状态之间的转换关系(即A状态转移k升水后变成B状态)建边,边权为转移的水的升数。然后用spfa求最短路。最后从d开始for到0,看一下那一个状态是可以到达的,然后输出即可。对于d>c的情况,直接输出0 c就可以了(因为无论如何杯子里最多只会有c升水,而且一开始的时候根本不用转移水就可以了)。因为数据范围是<=200,水的总和一定,所以只要知道前两个杯子的状态就能推出第三个杯子的状态,所以总点数会小于200*200(有些状态是不会出现的)。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#include<queue>
#define INF 0xfffffff
#define Maxn 210 struct node
{
int x,y,c,next;
}t[Maxn*Maxn*];int len; bool inq[Maxn*Maxn]; int first[Maxn*Maxn],dis[Maxn*Maxn]; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y,int c)
{
if(x==y) return;
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} queue<int > q; void spfa(int s)
{
memset(inq,,sizeof(inq));
memset(dis,,sizeof(dis));
while(!q.empty()) q.pop();
inq[s]=;dis[s]=;q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();inq[x]=;
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y])
{
q.push(y);
inq[y]=;
}
}
}
}
} int ffind(int x,int c,int C)
{
int mn=INF;
for(int i=;i<=c-x;i++)
{
mn=mymin(mn,dis[i*C+c-x-i]);//-,-,d
mn=mymin(mn,dis[(c-x-i)*C+i]);//-,-,d
mn=mymin(mn,dis[x*C+c-x-i]);//d,-,-
mn=mymin(mn,dis[x*C+i]);//d,-,-
mn=mymin(mn,dis[i*C+x]);//-,d,-
mn=mymin(mn,dis[(c-x-i)*C+x]);//-,d,-
}
return mn;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(d>=c) {printf("0 %d\n",c);continue;}
len=;
memset(first,,sizeof(first));
int C=c+;
for(int i=;i<=c;i++)
for(int j=;i+j<=c;j++)
{
int k=c-i-j,st=i*C+j;
if(i<=b-j) ins(st,i+j,i);else ins(st,(i-b+j)*C+b,b-j);//1->2
if(i<=c-k) ins(st,j,i);else ins(st,(i-c+k)*C+j,c-k);//1->3
if(j<=a-i) ins(st,(i+j)*C,j);else ins(st,a*C+j-a+i,a-i);//2->1
if(j<=c-k) ins(st,i*C,j);else ins(st,i*C+j-c+k,c-k);//2->3
if(k<=a-i) ins(st,(i+k)*C+j,k);else ins(st,a*C+j,a-i);//3->1
if(k<=b-j) ins(st,i*C+j+k,k);else ins(st,i*C+b,b-j);//3->2
}
spfa();
for(int i=d;i>=;i--)
{
int x=ffind(i,c,C);
if(x<INF) {printf("%d %d\n",x,i);break;}
}
}
return ;
}
[UVA10603]
2016-04-09 10:13:24
【UVA10603】Fill (构图+最短路)的更多相关文章
-
CF 787D Legacy(线段树思想构图+最短路)
D. Legacy time limit per test 2 seconds memory limit per test 256 megabytes input standard input out ...
-
UVa10603 Fill
解题思路:这是神奇的一题,一定要好好体会.见代码: #include<cstdio> #include<cstring> #include<algorithm> # ...
-
UVA-10603 Fill (BFS)
题目大意:有三个已知体积但不知刻度的杯子,前两个杯子中初始时没有水,第三个装满水,问是否可以倒出d升水,如果倒不出,则倒出一个最大的d’,使得d’<=d,并且在这个过程中要求总倒水量最少. 题目 ...
-
1.1.1最短路(Floyd、Dijstra、BellmanFord)
转载自hr_whisper大佬的博客 [ 一.Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路.所以Dijkstra常常作为其他算 ...
-
最短路算法详解(Dijkstra/SPFA/Floyd)
新的整理版本版的地址见我新博客 http://www.hrwhisper.me/?p=1952 一.Dijkstra Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路.所以Dijkst ...
-
【转】最短路&;差分约束题集
转自:http://blog.csdn.net/shahdza/article/details/7779273 最短路 [HDU] 1548 A strange lift基础最短路(或bfs)★254 ...
-
Altium中Fill,Polygon Pour,Plane的区别和用法
Fill:表示绘制一块实心的铜皮,将区域中的所有连线和过孔连接在一块,而不考虑是否属于同一个网络.假如所绘制的区域中有VCC和GND两个网络,用Fill命令会把这两个网络的元素连接在一起,这样就有可能 ...
-
转载 - 最短路&;差分约束题集
出处:http://blog.csdn.net/shahdza/article/details/7779273 最短路 [HDU] 1548 A strange lift基础最短路(或bfs)★ ...
-
最短路&;查分约束
[HDU] 1548 A strange lift 根蒂根基最短路(或bfs)★ 2544 最短路 根蒂根基最短路★ 3790 最短路径题目 根蒂根基最短路★ 2066 一小我的观光 根蒂根基最短路( ...
随机推荐
-
js控制文本框只能输入中文、英文、数字与指定特殊符号.
先在'' 里输入 onkeyup="value=value.replace(/[^\X]/g,'')" 然后在(/[\X]/g,'')里的 X换成你想输入的代码就可以了, 中文u4 ...
-
jmobile学习之路 ---- 视口
当我们的浏览器在窗口最大化的时候,此时屏幕的宽度,就是我们桌面的分辨率.这个规则仅仅适用于PC! 我们试图在iPhone中输出屏幕宽度,你会发现屏幕宽度是980!居然和PC屏幕差不多大! 苹果主导的这 ...
-
visual studio2015使用git管理源代码
1.注册https://git.oschina.net/ 2.注册好后,创建一个测试项目,如下图: 点击创建,如下: 上面的红框中的地址下面会用到. 3.git初始化设置 在本地电脑要安装git,打开 ...
-
自己的3dmax作品RX-105柯西高达
背后视角带导弹仓. 侧面. 侧后视角. 前侧视角. 斜前上视角 使用关联实现骨骼功能,头.躯干.肩.上臂.前臂.手腕.手指.腰.髋关节.踝关节.脚掌皆由骨骼(是通过多边形关联实现骨骼功能,而不是使用3 ...
-
BZOJ 3406 乳草的入侵
BFS. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm&g ...
-
SVN 冲突文件快速解决方法
精简的美丽...... 现在几乎没有几个写代码的人不用snv来存储代码了吧! 但是,在实际操作中,多人对同一文件读写造成冲突是时有发生的事.这个时候解决的方法就是打开文件找出冲突的地方.如果冲突的部分 ...
-
WCF HTTPS配置
昨天需要把做好的一个wcf服务发布到服务器站点下的一个虚拟目录中发布过程遇到了一个问题:服务器上的环境是https,因此需要多对配置文件修改于是在网上找啊找,遇到一个问题找一个问题,可是问题依然没解决 ...
-
c - 计算1到20的阶乘
#include <stdio.h> /* 题目:求 1+2!+3!+...+20!的和 */ unsigned long long int factorial(long n) { uns ...
-
一个用httpPost,get访问外网接口,参数json,返回json的示例
package com.royal.util; import java.io.BufferedReader;import java.io.DataInputStream;import java.io. ...
-
C语言 二维数组复制、清零及打印显示
#include <stdlib.h> #include <stdio.h> #include <string.h> //二维整型数组打印显示 ],int row, ...