[关闭]
@Metralix 2018-03-08T22:33:28.000000Z 字数 3989 阅读 862

寒假训练 DIV1（4）最短路及其应用2

A - Fill

最短路

题目大意

有三个杯子它们的容量分别是a,b,c, 并且初始状态下第一个和第二个是空的， 第三个杯子是满水的。可以把一个杯子的水倒入另一个杯子，当然，当被倒的杯子满了或者倒的杯子水完了，就不能继续倒了。
 你的任务是写一个程序计算出用最少的倒水量，使得其中一个杯子里有d升水。如果不能倒出d升水的话，那么找到一个d' < d ，使得d' 最接近d。

解题思路

 因为共有3个水杯， 根据每一杯的水量v1,v2,v3, 可以得到一个状态state(v1,v2,v3); 
 为了方便进行dfs搜索的状态转移，可以用两个三维数组volume[3], state[3]分别表示三个杯子的容量和状态。然后会有倒水的动作，可以从第1个杯子倒入第2，3个，从第2个倒入第1，3个等等……所以用两个for循环，可以遍历出所有的倒水方案。
然后注意一些不能倒水的条件，比如要倒的杯子是空的，目标杯子是满的，则不进行倒水的动作。

  1. #include<cstdio>
  2. #include<ctype.h>
  3. #include<algorithm>
  4. #include<iostream>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<cmath>
  9. #include<queue>
  10. #include<set>
  11. using namespace std;
  12. #define ll long long
  13. #define NMAX 20000
  14. typedef int state[3];
  15. state st[NMAX],a;
  16. int pour[NMAX];
  17. int record[205];
  18. int target;
  19. int vis[205][205],vispour[205][205];
  20. int try_to_insert(int x,int tpour)
  21. {
  22.     state &k = st[x];
  23.     if(vis[k[0]][k[1]] != 1 || vispour[k[0]][k[1]] > tpour)
  24.     {
  25.         vis[k[0]][k[1]] = 1;
  26.         vispour[k[0]][k[1]] = tpour;
  27.         return 1;
  28.     }
  29.     return 0;
  30. }
  31. int main()
  32. {
  33. //    freopen("input.txt","r",stdin);
  34. //    freopen("o.txt","w",stdout);
  35.     int i,j,t,ans;
  36.     scanf("%d",&t);
  37.     while(t--)
  38.     {
  39.         memset(record,0,sizeof(record));
  40.         memset(vis,0,sizeof(vis));
  41.         memset(vispour,0,sizeof(vis));
  42.         scanf("%d%d%d%d",&a[0],&a[1],&a[2],&target);
  43.         st[1][0] = st[1][1] = 0;
  44.         st[1][2] = a[2];
  45.         memset(pour,0,sizeof(pour));
  46.         record[a[2]] = 1;
  47.         int front = 1,rear = 2;
  48.         vis[0][0] = 1;
  49.         bool flag = false;
  50.         while(front < rear)
  51.         {
  52.             for(i = 0; i < 3; i++)
  53.                 if(record[st[front][i]] == 0 || pour[record[st[front][i]]] > pour[front])
  54.                     record[st[front][i]] = front;
  55.             for(i = 0; i < 3; i++)
  56.                 if(st[front][i] == target)
  57.                 {
  58.                     if(flag)
  59.                         ans = pour[ans] > pour[front]?front:ans;
  60.                     else
  61.                             ans = front;
  62.                     flag = true;
  63.                     break;
  64.                 }
  65.             for(i = 0; i < 3; i++)
  66.             {
  67.                 state &w = st[front];
  68.                 if(w[i] != 0)
  69.                 {
  70.                     for(j = 0; j < 3; j++)
  71.                     {
  72.                         if(i == j || (i != j && w[j] == a[j])) continue;
  73.                         state &temp = st[rear];
  74.                         memcpy(temp,w,sizeof(w));
  75.                         int pp;
  76.                         if(w[i] + w[j] > a[j])
  77.                         {
  78.                             pp = a[j] - w[j];
  79.                             temp[i] = w[i] - pp;
  80.                             temp[j] = a[j];
  81.                         }
  82.                         else
  83.                         {
  84.                             pp = w[i];
  85.                             temp[i] = 0;
  86.                             temp[j] = w[j] + pp;
  87.                         }
  88.                         int tpour;
  89.                             tpour = pour[front] + pp;
  90.                         if(try_to_insert(rear,tpour))
  91.                         {
  92.                             pour[rear] = tpour;
  93.                             rear++;
  94.                         }
  95.                     }
  96.                 }
  97.             }
  98.             front++;
  99.         }
  100.         if(record[target] == 0)
  101.         {
  102.             for(i = target; record[i] == 0; i--);
  103.             printf("%d %d\n",pour[record[i]],i);
  104.         }
  105.         else printf("%d %d\n",pour[ans],target);
  106.     }
  107.     return 0;
  108. }

B - Adventure of Super Mario

标签： spfa

题目大意

有n个村庄和m个城堡，村庄编号从1开始，城堡编号从n+1开始，一个人带着公主要从城堡n+m到村庄1，他还有一个魔法鞋可以有cnt次的使用机会可以让人能不花费时间走最多l，人只能在路上没有城堡的时候使用这个魔法鞋，问最少花费多少时间能到达村庄1。

解题思路

最短路径问题，用spfa算法，先用floyd将地点i到j的最短距离求出(不经过城堡)，然后用f[i][j]表示到达结点i还剩j次穿魔法鞋机会的花费时间，与普通的spfa不同的是加了一个判断:f[u][t1] > f[i][t1-1]，意味着从u到i用一次魔法鞋如果可以减短时间就用掉，并且如果不再队列中就加到队尾。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<string>
  4. #include<queue>
  5. #include<algorithm>
  6. #include<map>
  7. #include<stack>
  8. #include<iostream>
  9. #include<list>
  10. #include<set>
  11. #include<cmath>
  12. #define INF 0x7fffffff
  13. #define eps 1e-6
  14. #define LL long long
  15. using namespace std;
  16. int a,b,m,l,k,n;
  17. struct lx
  18. {
  19.     int v,len;
  20. };
  21. vector<lx>g[101];
  22. int dis[101][101];
  23. void SPFA(int start)
  24. {
  25.     queue<int>q;
  26.     bool vis[101];
  27.     memset(vis,0,sizeof(vis));
  29.     q.push(start);
  30.     vis[start]=1;
  31.     dis[start][start]=0;
  32.     while(!q.empty())
  33.     {
  34.         int u=q.front();q.pop();
  35.         vis[u]=0;
  37.         for(int j=0;j<g[u].size();j++)
  38.         {
  39.             int v=g[u][j].v;
  40.             int len=g[u][j].len;
  41.             if(dis[start][v]>dis[start][u]+len)
  42.             {
  43.                 dis[start][v]=dis[start][u]+len;
  44.                 if(v<=a&&!vis[v])
  45.                 {
  46.                     vis[v]=1;
  47.                     q.push(v);
  48.                 }
  49.             }
  50.         }
  51.     }
  52. }
  53. void spfa()
  54. {
  55.     bool vis[101];
  56.     int dp[101][11];
  57.     for(int i=0;i<101;i++)
  58.     {
  59.         vis[i]=0;
  60.         for(int j=0;j<11;j++)
  61.         dp[i][j]=INF;
  62.     }
  63.     queue<int>q;
  64.     q.push(n);
  65.     vis[n]=1;
  66.     dp[n][k]=0;
  67.     while(!q.empty())
  68.     {
  69.         int u=q.front();q.pop();
  70.         vis[u]=0;
  72.         for(int i=0;i<=k;i++)
  73.         {
  74.             for(int j=0;j<g[u].size();j++)
  75.             {
  76.                 int v=g[u][j].v;
  77.                 int len=g[u][j].len;
  78.                 if(dp[u][i]!=INF&&dp[v][i]>dp[u][i]+len)
  79.                 {
  80.                     dp[v][i]=dp[u][i]+len;
  81.                     if(!vis[v])
  82.                     {
  83.                         vis[v]=1;
  84.                         q.push(v);
  85.                     }
  86. //                    printf("%d > %d+%d\n",dp[v][i],dp[u][i],len);
  87. //                    dp[u][i]!=INF;注意
  88.                 }
  89.                 if(i==0)continue;
  90.                 for(v=1;v<=n;v++)
  91.                 {
  92.                     if(v!=u&&dis[u][v]<=l)
  93.                     {
  94.                         if(dp[v][i-1]>dp[u][i])
  95.                         {
  96.                             dp[v][i-1]=dp[u][i];
  97.                             if(!vis[v])
  98.                             {
  99.                                 vis[v]=1;
  100.                                 q.push(v);
  101.                             }
  102.                         }
  103.                     }
  104.                 }
  105.             }
  106.         }
  107.     }
  108.     int ans=INF;
  109.     for(int i=0;i<=k;i++)
  110.         ans=min(ans,dp[1][i]);
  111.     printf("%d\n",ans);
  112. }
  113. int main()
  114. {
  115.     int t;
  116.     scanf("%d",&t);
  117.     while(t--)
  118.     {
  119.         scanf("%d%d%d%d%d",&a,&b,&m,&l,&k);
  120.         for(int i=0;i<101;i++)
  121.             g[i].clear();
  122.         n=a+b;
  123.         int u,v,len;
  124.         while(m--)
  125.         {
  126.             scanf("%d%d%d",&u,&v,&len);
  127.             lx now;
  128.             now.len=len;
  129.             now.v=v,g[u].push_back(now);
  130.             now.v=u,g[v].push_back(now);
  131.         }
  132.         for(int i=0;i<101;i++)
  133.             for(int j=0;j<101;j++)
  134.             dis[i][j]=INF;
  136.         for(int i=1;i<=n;i++)
  137.         SPFA(i);
  139.         spfa();
  140.     }
  141. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注