本文共 1852 字，大约阅读时间需要 6 分钟。
Steiner Tree。概念就不讲了，引入0号结点。[1, n+m]到0连一条边，权重表示挖井的费用。这样建图spfa求MST即满足所求解。
1 /* 3311 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 typedef struct { 43 int v, w, nxt; 44 } edge_t; 45 46 const int INF = 0x3f3f3f3f; 47 const int maxst = 65; 48 const int maxn = 1010; 49 const int maxe = 13005; 50 edge_t E[maxe]; 51 int head[maxn], l; 52 int dp[maxn][maxst]; 53 bool visit[maxn][maxst]; 54 int n, m; 55 queue Q; 56 57 void init() { 58 l = 0; 59 memset(head, -1, sizeof(head)); 60 memset(dp, INF, sizeof(dp)); 61 memset(visit, false, sizeof(visit)); 62 } 63 64 void addEdge(int u, int v, int w) { 65 E[l].v = v; 66 E[l].w = w; 67 E[l].nxt = head[u]; 68 head[u] = l++; 69 70 E[l].v = u; 71 E[l].w = w; 72 E[l].nxt = head[v]; 73 head[v] = l++; 74 } 75 76 void spfa() { 77 int u, v, st, nst; 78 79 while (!Q.empty()) { 80 u = Q.front().fir; 81 st = Q.front().sec; 82 visit[u][st] = false; 83 Q.pop(); 84 for (int i=head[u]; i!=-1; i=E[i].nxt) { 85 v = E[i].v; 86 nst = st; 87 if (v <= n) 88 nst |= (1<
转载于:https://www.cnblogs.com/bombe1013/p/5065332.html