有什么推荐的网站,婚纱摄影网站大全,黑龙江骏域建设网站专家,在线自动翻译整个网页1 /*2 题意#xff1a;有 n 个站点#xff08;编号1...n#xff09;#xff0c;每一个站点都有一个能量值#xff0c;为了不让这些能量值连接起来#xff0c;要用 3 坦克占领这个站点#xff01;已知站点的 之间的距离#xff0c;每个坦克从0点出发到某一个站点有 n 个站点编号1...n每一个站点都有一个能量值为了不让这些能量值连接起来要用 3 坦克占领这个站点已知站点的 之间的距离每个坦克从0点出发到某一个站点1 unit distance costs 1 unit oil4 最后占领的所有的站点的能量值之和为总能量值的一半还要多问最少耗油多少5 6 */7 8 /*9 思路不同的坦克会占领不同的站点耗油最少那就是路程最少所以我们先将从 0点到其他各点的10 最短距离求出来也就是d[i]的值然后我们又知道每一个站点的所具有的能量值也就是w[i];11 最后求出满足占领站点的能量比总能量的一半多并且路程最少。。。直接01背包走起 12 */ 13 #includeiostream14 #includequeue15 #includecstring16 #includecstdio17 #includealgorithm18 #includevector19 #define N 1000520 #define INF 0x3f3f3f3f21 using namespace std;22 23 int w[105];24 25 struct EDGE{26 int u, v, nt, dist;27 EDGE(){}28 29 EDGE(int u, int v, int nt, int dist){30 this-uu;31 this-vv;32 this-ntnt;33 this-distdist;34 }35 };36 37 EDGE edge[N*2];38 int first[105];39 int cnt;40 queuepairint, int q;41 int n, m;42 int dp[10005];43 int d[105];44 int map[105][105];45 46 void addEdge(int u, int v, int dist){47 edge[cnt]EDGE(u, v, first[u], dist);48 first[u]cnt-1;49 edge[cnt]EDGE(v, u, first[v], dist);50 first[v]cnt-1;51 }52 53 void Dijkstra(){54 d[0]0;55 q.push(make_pair(0, 0)); 56 while(!q.empty()){57 pairint,int curq.front();58 q.pop();59 int ucur.second;60 if(d[u] ! cur.first) continue;61 for(int efirst[u]; e!-1; eedge[e].nt){62 int vedge[e].v, distedge[e].dist;63 if(d[v] d[u] dist){64 d[v] d[u] dist;65 q.push(make_pair(d[v], v));66 }67 }68 }69 }70 71 int main(){72 int t;73 int sumP, sumD;74 scanf(%d, t);75 while(t--){76 scanf(%d%d, n, m);77 cnt0;78 memset(d, 0x3f, sizeof(d));79 memset(first, -1, sizeof(first));80 for(int i0; in; i)81 for(int j0; jn; j)82 map[i][j]INF;83 while(m--){84 int u, v, dist;85 scanf(%d%d%d, u, v, dist);86 if(map[u][v]dist)87 map[u][v]map[v][u]dist;88 }89 for(int i0; in; i)90 for(int j0; ji; j)91 if(map[i][j]!INF)92 addEdge(i, j, map[i][j]); 93 Dijkstra();//求出 0点到其他个点的最短的距离 94 sumPsumD0;95 for(int i1; in; i){96 scanf(%d, w[i]);97 sumPw[i];98 sumDd[i];99 }
100 memset(dp, 0x3f, sizeof(dp));//初始背包的总价值为无穷大
101 dp[0]0;
102
103 //zeroOnePackage... d[i]相当于价值也就是耗油量 w[i]相当于容积也就是能量值
104 for(int i1; in; i)
105 for(int jsumP; jw[i]; --j)
106 dp[j]min(dp[j], dp[j-w[i]]d[i]);
107
108 int maxCostINF;
109 for(int isumP/21; isumP; i)//注意是sumP/21(因为要比一半多)
110 if(maxCostdp[i])
111 maxCostdp[i];
112 if(maxCostINF)
113 printf(impossible\n);
114 else printf(%d\n, maxCost);
115 }
116 return 0;
117 }
118 119 /*
120 思路dp[i][j]表示到达 i站点 并且占领的能量值为 j时的耗油最小值
121 开始想用的是spfa算法并且在进行节点之间距离松弛的时候也将 背包融进来但是超时啊
122 好桑心.....
123 */
124
125 #includeiostream
126 #includequeue
127 #includecstring
128 #includecstdio
129 #includealgorithm
130 #includevector
131 #define N 10005
132 #define INF 0x3f3f3f3f
133 using namespace std;
134
135 int w[105];
136
137 struct EDGE{
138 int u, v, nt, dist;
139 EDGE(){}
140
141 EDGE(int u, int v, int nt, int dist){
142 this-uu;
143 this-vv;
144 this-ntnt;
145 this-distdist;
146 }
147 };
148
149 EDGE edge[N*2];
150 int first[105];
151 int cnt;
152 queuepairint, int q;
153 int vis[105];
154 int n, m, sum;
155 int dp[105][10005];
156 int map[105][105];
157
158 void addEdge(int u, int v, int dist){
159 edge[cnt]EDGE(u, v, first[u], dist);
160 first[u]cnt-1;
161 edge[cnt]EDGE(v, u, first[v], dist);
162 first[v]cnt-1;
163 }
164
165 void spfa(){
166 dp[0][0]0;
167 q.push(make_pair(0, 0));
168 vis[0]1;
169 while(!q.empty()){
170 pairint,int curq.front();
171 q.pop();
172 int ucur.second;
173 vis[u]0;
174 for(int efirst[u]; e!-1; eedge[e].nt){
175 int vedge[e].v, distedge[e].dist;
176 for(int jw[v]; jsum; j)
177 if(dp[v][j] dp[u][j-w[v]] dist){
178 dp[v][j] dp[u][j-w[v]] dist;
179 if(!vis[v]){
180 vis[v]1;
181 q.push(make_pair(dp[v][j], v));
182 }
183 }
184 }
185 }
186 }
187
188 int main(){
189 int t;
190 scanf(%d, t);
191 while(t--){
192 scanf(%d%d, n, m);
193 cnt0;
194 memset(first, -1, sizeof(first));
195 for(int i0; in; i)
196 for(int j0; jn; j)
197 map[i][j]INF;
198 while(m--){
199 int u, v, dist;
200 scanf(%d%d%d, u, v, dist);
201 if(map[u][v]dist)
202 map[u][v]map[v][u]dist;
203 }
204 for(int i0; in; i)
205 for(int j0; jn; j)
206 if(map[i][j]!INF)
207 addEdge(i, j, map[i][j]);
208 for(int i1; in; i){//最后将1...n节点的最优值汇聚到 第 n1个节点上
209 edge[cnt]EDGE(i, n1, first[i], 0);
210 first[i]cnt-1;
211 }
212 sum0;
213 for(int i1; in; i){
214 scanf(%d, w[i]);
215 sumw[i];
216 }
217 w[n1]0;
218 for(int i0; in2; i)
219 for(int j0; jsum2; j)
220 dp[i][j]INF;
221 spfa();
222 int maxCostINF;
223 for(int isum/21; isum; i)
224 if(maxCostdp[n1][i])
225 maxCostdp[n1][i];
226 if(maxCostINF)
227 printf(impossible\n);
228 else printf(%d\n, maxCost);
229 }
230 return 0;
231 } 转载于:https://www.cnblogs.com/hujunzheng/p/3913288.html
