本文共 1894 字，大约阅读时间需要 6 分钟。

题目大意：自己看中文。。。

思路：不难发现，题目等价于让我们求出一些标号上升的子序列精确覆盖全集，每一个子序列的起点一定是利用“能力爆发”   得到的。

那么我们只需对于每个星球，确定一个前驱就可以了。

若是0作为前驱，则转移代价为定位时间；否则转移代价为路径长度。此外一个点的前驱的标号严格小于自己的标号。

注意0可以作为多个星球的前驱，剩下的星球只能作为一个星球的前驱。

于是转化为类二分图最优匹配问题，利用最小费用流求解即可。

Code:

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;queue
        
          q;#define N 810struct Solver { int head[N<<1], next[N*N], end[N*N], flow[N*N], cost[N*N], ind; int d[N<<1], ld[N<<1], lb[N<<1]; bool inq[N<<1]; void reset() { ind = 0; memset(head, -1, sizeof head); } void addedge(int a, int b, int _flow, int _cost) { int q = ind++; end[q] = b; next[q] = head[a]; head[a] = q; flow[q] = _flow; cost[q] = _cost; } void make(int a, int b, int _flow, int _cost) { addedge(a, b, _flow, _cost); addedge(b, a, 0, -_cost); } bool spfa(int S, int T) { memset(d, 0x3f, sizeof d); d[S] = 0; inq[S] = 1; q.push(S); int i, j; while(!q.empty()) { i = q.front(); q.pop(); inq[i] = 0; for(j = head[i]; j != -1; j = next[j]) { if (flow[j] && d[end[j]] > d[i] + cost[j]) { d[end[j]] = d[i] + cost[j]; ld[end[j]] = i; lb[end[j]] = j; if (!inq[end[j]]) inq[end[j]] = 1, q.push(end[j]); } } } return d[T] != 0x3f3f3f3f; } int Mincost(int S, int T) { int res = 0, Min, i; while(spfa(S, T)) { Min = 0x3f3f3f3f; for(i = T; i != S; i = ld[i]) Min = Min > flow[lb[i]] ? flow[lb[i]] : Min; for(i = T; i != S; i = ld[i]) flow[lb[i]] -= Min, flow[lb[i] ^ 1] += Min; res += Min * d[T]; } return res; }}G;int main() { int n, m; scanf("%d%d", &n, &m); register int i; int x; G.reset(); for(i = 1; i <= n; ++i) { scanf("%d", &x); G.make(1, i<<1^1, 1, x); } int a, b; for(i = 1; i <= m; ++i) { scanf("%d%d%d", &a, &b, &x); if (a > b) swap(a, b); G.make(a<<1, b<<1^1, 1, x); } G.make(0, 1, 0x3f3f3f3f, 0); for(i = 1; i <= n; ++i) G.make(0, i<<1, 1, 0), G.make(i<<1^1, 2*n+2, 1, 0); printf("%d\n", G.Mincost(0, 2*n+2)); return 0;}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/wyfcyx_forever/article/details/40430297 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！