[BZOJ2502]清理雪道-白红宇

[BZOJ2502]清理雪道

阅读量：4943 次

发布时间：2019-06-11

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

[BZOJ2502]清理雪道

试题描述

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

输入

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为m_i (0 <= m_i < n) ，后面共有m_i个整数，由空格隔开，每个整数a_ij互不相同，代表从地点i下降到地点a_ij的斜坡。每个地点至少有一个斜坡与之相连。

输出

输出文件的第一行是一个整数

k – 直升飞机的最少飞行次数。

输入示例

81 31 72 4 51 81 802 6 50

输出示例

数据规模及约定

见“输入”

题解

最小费用流。从源点向入度为 0 的点连容量无穷费用为 0 的有向边，从出度为 0 的点向汇点连容量无穷费用为 0 的有向边；然后对于这张 DAG 的每条有向边，拆分成两条同方向的有向边，一条容量为 1 费用负无穷，另一条容量无穷费用为 0. 因为我们需要强制每条边至少经过一次，所以要将其中一条的费用设成负无穷。

跑一边最小费用流（注意不是最大流）即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); } return x * f;}#define maxn 110#define maxm 40010#define oo 2147483647#define inf 100000#define LL long longstruct Edge { int from, to, flow, cost; } ;struct ZKW { int n, m, s, t, head[maxn], next[maxm]; LL cost, ans; Edge es[maxm]; bool inq[maxn]; LL d[maxn]; bool vis[maxn]; void init(int nn) { n = nn; m = 0; memset(head, -1, sizeof(head)); return ; } void AddEdge(int a, int b, int c, int d) { es[m] = (Edge){ a, b, c, d }; next[m] = head[a]; head[a] = m++; es[m] = (Edge){ b, a, 0, -d }; next[m] = head[b]; head[b] = m++; return ; } bool BFS() { memset(inq, 0, sizeof(inq)); for(int i = 1; i <= n; i++) d[i] = oo; deque 
                
                  Q; Q.push_front(t); inq[t] = 1; d[t] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop_front(); inq[u] = 0; for(int i = head[u]; i != -1; i = next[i]) { Edge& e = es[i^1]; if(e.flow && d[e.from] > d[u] + e.cost) { d[e.from] = d[u] + e.cost; if(!inq[e.from]) { inq[e.from] = 1; if(Q.empty() || d[e.from] <= d[Q.front()]) Q.push_front(e.from); else Q.push_back(e.from); } } } } if(d[s] == oo) return 0; for(int i = 0; i < m; i++) es[i].cost += d[es[i].to] - d[es[i].from]; cost += d[s]; return 1; } int DFS(int u, int a) { if(u == t || !a){ ans += cost * a; return a; } vis[u] = 1; int flow = 0, f; for(int i = head[u]; i != -1; i = next[i]) { Edge& e = es[i]; if(!vis[e.to] && e.flow && !e.cost && (f = DFS(e.to, min(a, e.flow)))) { a -= f; flow += f; e.flow -= f; es[i^1].flow += f; if(!a) return flow; } } return flow; } int MaxFlow(int ss, int tt) { s = ss; t = tt; int flow = 0, tmp; while(BFS()) { if(cost >= 0) break; do { memset(vis, 0, sizeof(vis)); tmp = DFS(s, oo); flow += tmp; } while(tmp); } return flow; }} sol;int in[maxn], out[maxn];int main() { int n = read(), s = n + 1, t = s + 1; sol.init(n + 2); for(int i = 1; i <= n; i++) { int m = read(); while(m--) { int a = read(); in[a]++; out[i]++; sol.AddEdge(i, a, 1, -inf); sol.AddEdge(i, a, oo, 0); } } for(int i = 1; i <= n; i++) { if(!in[i]) sol.AddEdge(s, i, oo, 0); if(!out[i]) sol.AddEdge(i, t, oo, 0); } printf("%d\n", sol.MaxFlow(s, t)); return 0;}

转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/5732155.html

你可能感兴趣的文章