/*
题意：有 n 个站点（编号1...n），每一个站点都有一个能量值，为了不让这些能量值连接起来，要用
坦克占领这个站点！已知站点的 之间的距离，每个坦克从0点出发到某一个站点，1 unit distance costs 1 unit oil！
最后占领的所有的站点的能量值之和为总能量值的一半还要多，问最少耗油多少！
*/
/*
思路：不同的坦克会占领不同的站点，耗油最少那就是路程最少，所以我们先将从 0点到其他各点的
最短距离求出来！也就是d[i]的值！然后我们又知道每一个站点的所具有的能量值！也就是w[i];
最后求出满足占领站点的能量比总能量的一半多并且路程最少。。。直接01背包走起！
*/
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;
int w[105];
struct EDGE{
int u, v, nt, dist;
EDGE(){}
EDGE(int u, int v, int nt, int dist){
this->u=u;
this->v=v;
this->nt=nt;
this->dist=dist;
}
};
EDGE edge[N*2];
int first[105];
int cnt;
queue<pair<int, int> >q;
int n, m;
int dp[10005];
int d[105];
int map[105][105];
void addEdge(int u, int v, int dist){
edge[cnt++]=EDGE(u, v, first[u], dist);
first[u]=cnt-1;
edge[cnt++]=EDGE(v, u, first[v], dist);
first[v]=cnt-1;
}
void Dijkstra(){
d[0]=0;
q.push(make_pair(0, 0));
while(!q.empty()){
pair<int,int> cur=q.front();
q.pop();
int u=cur.second;
if(d[u] != cur.first) continue;
for(int e=first[u]; e!=-1; e=edge[e].nt){
int v=edge[e].v, dist=edge[e].dist;
if(d[v] > d[u] + dist){
d[v] = d[u] + dist;
q.push(make_pair(d[v], v));
}
}
}
}
int main(){
int t;
int sumP, sumD;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
cnt=0;
memset(d, 0x3f, sizeof(d));
memset(first, -1, sizeof(first));
for(int i=0; i<=n; ++i)
for(int j=0; j<=n; ++j)
map[i][j]=INF;
while(m--){
int u, v, dist;
scanf("%d%d%d", &u, &v, &dist);
if(map[u][v]>dist)
map[u][v]=map[v][u]=dist;
}
for(int i=0; i<=n; ++i)
for(int j=0; j<=i; ++j)
if(map[i][j]!=INF)
addEdge(i, j, map[i][j]);
Dijkstra();//求出 0点到其他个点的最短的距离！
sumP=sumD=0;
for(int i=1; i<=n; ++i){
scanf("%d", &w[i]);
sumP+=w[i];
sumD+=d[i];
}
memset(dp, 0x3f, sizeof(dp));//初始背包的总价值为无穷大
dp[0]=0;
//zeroOnePackage... d[i]相当于价值（也就是耗油量）， w[i]相当于容积（也就是能量值）
for(int i=1; i<=n; ++i)
for(int j=sumP; j>=w[i]; --j)
dp[j]=min(dp[j], dp[j-w[i]]+d[i]);
int maxCost=INF;
for(int i=sumP/2+1; i<=sumP; ++i)//注意是sumP/2+1(因为要比一半多)
if(maxCost>dp[i])
maxCost=dp[i];
if(maxCost==INF)
printf("impossible\n");
else printf("%d\n", maxCost);
}
return 0;
}
/*
思路：dp[i][j]表示到达 i站点， 并且占领的能量值为 j时的耗油最小值！
开始想用的是spfa算法，并且在进行节点之间距离松弛的时候，也将 背包融进来，但是超时啊！
好桑心.....
*/
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;
int w[105];
struct EDGE{
int u, v, nt, dist;
EDGE(){}
EDGE(int u, int v, int nt, int dist){
this->u=u;
this->v=v;
this->nt=nt;
this->dist=dist;
}
};
EDGE edge[N*2];
int first[105];
int cnt;
queue<pair<int, int> >q;
int vis[105];
int n, m, sum;
int dp[105][10005];
int map[105][105];
void addEdge(int u, int v, int dist){
edge[cnt++]=EDGE(u, v, first[u], dist);
first[u]=cnt-1;
edge[cnt++]=EDGE(v, u, first[v], dist);
first[v]=cnt-1;
}
void spfa(){
dp[0][0]=0;
q.push(make_pair(0, 0));
vis[0]=1;
while(!q.empty()){
pair<int,int> cur=q.front();
q.pop();
int u=cur.second;
vis[u]=0;
for(int e=first[u]; e!=-1; e=edge[e].nt){
int v=edge[e].v, dist=edge[e].dist;
for(int j=w[v]; j<=sum; ++j)
if(dp[v][j] > dp[u][j-w[v]] + dist){
dp[v][j] = dp[u][j-w[v]] + dist;
if(!vis[v]){
vis[v]=1;
q.push(make_pair(dp[v][j], v));
}
}
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
cnt=0;
memset(first, -1, sizeof(first));
for(int i=0; i<=n; ++i)
for(int j=0; j<=n; ++j)
map[i][j]=INF;
while(m--){
int u, v, dist;
scanf("%d%d%d", &u, &v, &dist);
if(map[u][v]>dist)
map[u][v]=map[v][u]=dist;
}
for(int i=0; i<=n; ++i)
for(int j=0; j<=n; ++j)
if(map[i][j]!=INF)
addEdge(i, j, map[i][j]);
for(int i=1; i<=n; ++i){//最后将1...n节点的最优值汇聚到 第 n+1个节点上
edge[cnt++]=EDGE(i, n+1, first[i], 0);
first[i]=cnt-1;
}
sum=0;
for(int i=1; i<=n; ++i){
scanf("%d", &w[i]);
sum+=w[i];
}
w[n+1]=0;
for(int i=0; i<n+2; ++i)
for(int j=0; j<sum+2; ++j)
dp[i][j]=INF;
spfa();
int maxCost=INF;
for(int i=sum/2+1; i<=sum; ++i)
if(maxCost>dp[n+1][i])
maxCost=dp[n+1][i];
if(maxCost==INF)
printf("impossible\n");
else printf("%d\n", maxCost);
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3913288.html，如需转载请自行联系原作者
