北京营销型网站建站公司青岛seo服务哪家好
1003: [ZJOI2006]物流运输
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 10636 Solved: 4744
[Submit][Status][Discuss]
Description
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本
尽可能地小。
Input
第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示
每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编
号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来
一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1< = a < = b < = n）。表示编号为P的码
头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一
条从码头A到码头B的运输路线。
Output
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。
Sample Input
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
Sample Output
//前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32
HINT
Source
HOME Back
好像没人做法和我一样的，水一波状压dp
先预处理出选的点集为iii的最短路为E，这可以通过求出最小生成树
如果没有1或m，或不连通显然不合法，赋一个极大值
然后设fi,jf_{i,j}fi,j表示到了第i天，当前的路径为j的最小代价
如果j中有码头在维修，就赋极大值
不然如果不改变路径，fi,j=fi−1,j+Ejf_{i,j}=f_{i-1,j}+E_jfi,j=fi−1,j+Ej
改变路径，从前一天最优的转移过来，fi,j=Mn+Ej+Kf_{i,j}=Mn+E_j+Kfi,j=Mn+Ej+K
数组要滚存
#include <cstdio>
#include <algorithm>
using namespace std;#define dd c=getchar()
int read() {int s=0,w=1;char c;while (dd,c>'9' || c<'0') if (c=='-') w=-1;while (c>='0' && c<='9') s=s*10+c-'0',dd;return s*w;}
#undef dd
void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
void wln(int x) {write(x);putchar('\n');}void wsp(int x) {write(x);putchar(' ');}const int N = 105,Mx = 1<<20;
int D,n,K,m,Q;
struct edge {int u, v, w;bool operator < (edge a) const{return w < a.w;}
}e[N*7];
int fa[N],can[N],E[Mx],f[2][Mx];int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int main() {
// freopen("1003.in", "r", stdin);
// freopen("1003.out", "w", stdout);D = read(); n = read(); K = read(); m = read();for (int i = 1; i <= m; i++) {e[i] = (edge) {read()-1, read()-1, read()};}sort(e+1, e+m+1);for (int i = 0; i < 1<<n; i++) {int s = 0;if (!(i&1) || !(i>>(n-1)&1)) {E[i] = 1e9; continue;}for (int j = 0; j < n; j++) {fa[j] = j;if (i >> j&1) s++;}for (int j = 1; j <= m; j++) {if (!(i>>e[j].u&1) || !(i>>e[j].v&1)) continue;int u = find(e[j].u), v = find(e[j].v);if (u != v) s--, fa[u] = v, E[i]+=e[j].w;}if (s!=1) E[i] = 1e9;}for (int i = 1; i <= D; i++) can[i] = (1<<n)-1;Q = read();for (int i = 1, x, l, r; i <= Q; i++) {x = read()-1, l = read(), r = read();for (int j = l; j <= r; j++) can[j]^=1<<x;}int la=0,Mn=0;for (int i = 1, p = 0; i <= D; i++, p^=1) {la = Mn; Mn = 1e9;for (int j = 0; j < 1<<n; j++) {if ((can[i]&j) != j) f[p][j] = 1e9;else {f[p][j] = min(f[!p][j], la+K)+E[j];Mn = min(Mn, f[p][j]);}}}wln(Mn);
}