HDU - 3339 In Action（dijkstra+01背包）

看題目戳我

題目大意：

       有n個發電站，m條路，每條路有各自的距離，每個發電站有各自的發電量，現在需要炸毀它們，一輛坦克隻能炸毀一個發電站，而且需要炸毀的發電廠的發電量需要大于所有發電站所産生的總電量的一半，求坦克走的最短距離。

題目思路：

      看完這個題目一個比較容易産生的想法就是：求出源點到達其他點的最短距離，然後把距離從小到大排隊，看到達哪個點（即哪個路線）炸毀的發電量可以達到要求。

      下面比較明顯的就是，想要求出源點到達每個其他點的距離，dijkstra當然是首選。

      接下來就是如何判斷這條路徑能不能達到要求。

      我們可以抽象出來（好吧也并不是很抽象），思路反一下，走這麼長的距離最多可以炸毀多少發電量。這樣是不是有點眼熟了呢？——跟背包問題有點像。把到每個點走的路長當作背包的體積，炸毀的發電量是每次可以裝進去的價值。然後，bingo！

其他細節見代碼

題目代碼：

##include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#define maxn 10005
#define INF 0x3f3f3f3f

using namespace std;
int dis[105];
int f[80050];//dp用的
struct Edge
{
     int u,v,w;
     Edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){}
};
struct Node
{
     int id;
     int w;
     bool operator<(const Node &b)
          const{w>b.w;}
}mid;
struct P
{
     int po;
     int d;
}poww[105];
vector<Edge>e[maxn];
priority_queue<Node>pq;

int cmp(P a,P b)
{
     return a.d<b.d;
}
void dijk(int s)//dijkstra模闆求出最短路
{
     pq.push(Node{s,0});
     dis[s]=0;
     while(!pq.empty())
     {
          mid=pq.top();
          pq.pop();
          int card=mid.id;
          if(mid.w!=dis[card])
               continue;
          for(int i=0;i<e[card].size();i++)
          {
               //printf("%d---%d----%d\n",card,dis[card],e[card][i].v);
               if(dis[e[card][i].v]>dis[card]+e[card][i].w)
               {
                    dis[e[card][i].v]=dis[card]+e[card][i].w;
                    pq.push(Node{e[card][i].v,dis[e[card][i].v]});
                    //printf("%d-----------------------%d\n",dis[card],e[card][i].w);
               }
          }
     }
}
int main(void)
{
     int t;
     int n,m;
     int a,b,c;
     double tol;
     scanf("%d",&t);
     while(t--)
     {
          //cout<<0x3f3f3f3f<<endl;
          scanf("%d%d",&n,&m);
          memset(dis,0x3f,sizeof(dis));//初始化請注意
          memset(f,0,sizeof(f));
          memset(poww,0,sizeof(poww));
          for(int i=0;i<=n;i++)
               e[i].clear();
          //
          for(int i=0;i<m;i++)
          {
               scanf("%d%d%d",&a,&b,&c);
               e[a].push_back(Edge{a,b,c});
               e[b].push_back(Edge{b,a,c});
          }
          dijk(0);
          //以上求出最短路
          //print(n);
          int sum=0;
          int oil=0,p=0;
          for(int i=1;i<=n;i++)
          {
               scanf("%d",&poww[i].po);//價值
               sum+=poww[i].po;
               if(dis[i]<INF)
               {
                    oil+=dis[i];
                    p++;
               }
               poww[i].d=dis[i];//體積
          }
          //print(n);
          sort(poww+1,poww+n+1,cmp);
          //可用油量為j的時候可以獲得多少能量
          for(int i=1;i<=p;i++)
          {
               for(int j=oil;j>=poww[i].d;j--)//注意如何把各個發電站的“體積”和“價值”對應起來，用P結構體
               {
                    f[j]=max(f[j],f[j-poww[i].d]+poww[i].po);//依次獲得相應油量下可以有多少價值
               }
          }
          int i;
          for(i=0;i<=oil;i++)
          {
               if(f[i]>=(sum/2+1))
                    break;
          }
          if(i<=oil)
               printf("%d\n",i);
          else
               printf("impossible\n");
     }
     return 0;
}
/*
2
5 7
0 2 6
0 1 4
0 1 2
2 3 3
3 4 1
3 5 6
4 5 7
6 12 4 3 2
*/
           

呼呼