【UVA10603】Fill （构图+最短路）

题目：

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（有些状态是不会出现的）。

代码如下：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 #include<queue>
  8 #define INF 0xfffffff
  9 #define Maxn 210
 10 
 11 struct node
 12 {
 13     int x,y,c,next;
 14 }t[Maxn*Maxn*10];int len;
 15 
 16 bool inq[Maxn*Maxn];
 17 
 18 int first[Maxn*Maxn],dis[Maxn*Maxn];
 19 
 20 int mymin(int x,int y) {return x<y?x:y;}
 21 
 22 void ins(int x,int y,int c)
 23 {
 24     if(x==y) return;
 25     t[++len].x=x;t[len].y=y;t[len].c=c;
 26     t[len].next=first[x];first[x]=len;
 27 }
 28 
 29 queue<int > q;
 30 
 31 void spfa(int s)
 32 {
 33     memset(inq,0,sizeof(inq));
 34     memset(dis,63,sizeof(dis));
 35     while(!q.empty()) q.pop();
 36     inq[s]=1;dis[s]=0;q.push(s);
 37     while(!q.empty())
 38     {
 39         int x=q.front();q.pop();inq[x]=0;
 40         for(int i=first[x];i;i=t[i].next)
 41         {
 42             int y=t[i].y;
 43             if(dis[y]>dis[x]+t[i].c)
 44             {
 45                 dis[y]=dis[x]+t[i].c;
 46                 if(!inq[y])
 47                 {
 48                     q.push(y);
 49                     inq[y]=1;
 50                 }
 51             }
 52         }
 53     }
 54 }
 55 
 56 int ffind(int x,int c,int C)
 57 {
 58     int mn=INF;
 59     for(int i=1;i<=c-x;i++)
 60     {
 61         mn=mymin(mn,dis[i*C+c-x-i]);//-,-,d
 62         mn=mymin(mn,dis[(c-x-i)*C+i]);//-,-,d
 63         mn=mymin(mn,dis[x*C+c-x-i]);//d,-,-
 64         mn=mymin(mn,dis[x*C+i]);//d,-,-
 65         mn=mymin(mn,dis[i*C+x]);//-,d,-
 66         mn=mymin(mn,dis[(c-x-i)*C+x]);//-,d,-
 67     }
 68     return mn;
 69 }
 70 
 71 int main()
 72 {
 73     int T;
 74     scanf("%d",&T);
 75     while(T--)
 76     {
 77         int a,b,c,d;
 78         scanf("%d%d%d%d",&a,&b,&c,&d);
 79         if(d>=c) {printf("0 %d
",c);continue;}
 80         len=0;
 81         memset(first,0,sizeof(first));
 82         int C=c+1;
 83         for(int i=0;i<=c;i++)
 84          for(int j=0;i+j<=c;j++)
 85          {
 86             int k=c-i-j,st=i*C+j;
 87             if(i<=b-j) ins(st,i+j,i);else ins(st,(i-b+j)*C+b,b-j);//1->2
 88             if(i<=c-k) ins(st,j,i);else ins(st,(i-c+k)*C+j,c-k);//1->3
 89             if(j<=a-i) ins(st,(i+j)*C,j);else ins(st,a*C+j-a+i,a-i);//2->1
 90             if(j<=c-k) ins(st,i*C,j);else ins(st,i*C+j-c+k,c-k);//2->3
 91             if(k<=a-i) ins(st,(i+k)*C+j,k);else ins(st,a*C+j,a-i);//3->1
 92             if(k<=b-j) ins(st,i*C+j+k,k);else ins(st,i*C+b,b-j);//3->2
 93          }
 94          spfa(0);
 95          for(int i=d;i>=0;i--)
 96          {
 97              int x=ffind(i,c,C);
 98              if(x<INF) {printf("%d %d
",x,i);break;}
 99          }
100     }
101     return 0;
102 }

[UVA10603]

2016-04-09 10:13:24