洛谷P4843 清理雪道

题意：给你DAG，求最小路径边覆盖。路径可重。

解：首先可以想到边转点，发现有n²条边，果断超时。

有源汇有上下界最小流。

建图：每条边都建立一条边，流量限制为[1, 1]。

源点向每个点连边，因为都可以作为起点。流量不限。

每个点向汇点连边，同上。

求最小可行流。

首先去掉下界限制，跑出一个可行流。

然后求t -> s的最大流，退掉多余流。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <queue>
  4 #include <cstring>
  5 
  6 const int N = 10010, M = 1000010, INF = 0x3f3f3f3f;
  7 
  8 struct Edge {
  9     int nex, v, c;
 10 }edge[N << 1]; int top = 1;
 11 
 12 int e[N], d[N], ot[N];
 13 std::queue<int> Q;
 14 
 15 inline void add(int x, int y, int z) {
 16     top++;
 17     edge[top].v = y;
 18     edge[top].c = z;
 19     edge[top].nex = e[x];
 20     e[x] = top;
 21 
 22     top++;
 23     edge[top].v = x;
 24     edge[top].c = 0;
 25     edge[top].nex = e[y];
 26     e[y] = top;
 27     return;
 28 }
 29 
 30 inline bool BFS(int s, int t) {
 31     memset(d, 0, sizeof(d));
 32     d[s] = 1;
 33     Q.push(s);
 34     while(!Q.empty()) {
 35         int x = Q.front();
 36         Q.pop();
 37         for(int i = e[x]; i; i = edge[i].nex) {
 38             int y = edge[i].v;
 39             if(!edge[i].c || d[y]) {
 40                 continue;
 41             }
 42             d[y] = d[x] + 1;
 43             Q.push(y);
 44         }
 45     }
 46     return d[t];
 47 }
 48 
 49 int DFS(int x, int t, int maxF) {
 50     if(x == t) {
 51         return maxF;
 52     }
 53     int ans = 0;
 54     for(int i = e[x]; i; i = edge[i].nex) {
 55         int y = edge[i].v;
 56         if(!edge[i].c || d[x] + 1 != d[y]) {
 57             continue;
 58         }
 59         int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
 60         if(!temp) {
 61             d[y] = INF;
 62         }
 63         ans += temp;
 64         edge[i].c -= temp;
 65         edge[i ^ 1].c += temp;
 66         if(ans == maxF) {
 67             break;
 68         }
 69     }
 70     return ans;
 71 }
 72 
 73 inline int solve(int s, int t) {
 74     int ans = 0;
 75     while(BFS(s, t)) {
 76         ans += DFS(s, t, INF);
 77     }
 78     return ans;
 79 }
 80 
 81 int main() {
 82 
 83     int n;
 84     scanf("%d", &n);
 85     int s = n + 1, t = n + 2;
 86     for(int i = 1, x, y; i <= n; i++) {
 87         scanf("%d", &x);
 88         for(int j = 1; j <= x; j++) {
 89             scanf("%d", &y);
 90             add(i, y, INF);
 91             ot[i]++;
 92             ot[y]--;
 93         }
 94         add(s, i, INF);
 95         add(i, t, INF);
 96     }
 97     int ss = n + 3, tt = n + 4, sum = 0;
 98     for(int i = 1; i <= n; i++) {
 99         if(ot[i] > 0) {
100             add(i, tt, ot[i]);
101             sum += ot[i];
102         }
103         else if(ot[i] < 0) {
104             add(ss, i, -ot[i]);
105         }
106     }
107     add(t, s, INF);
108     solve(ss, tt);
109     int ans;
110     for(int i = e[s]; i; i = edge[i].nex) {
111         if(edge[i].v == t) {
112             ans = edge[i].c;
113             break;
114         }
115     }
116     for(int i = e[ss]; i; i = edge[i].nex) {
117         edge[i].c = edge[i ^ 1].c = 0;
118     }
119     for(int i = e[tt]; i; i = edge[i].nex) {
120         edge[i].c = edge[i ^ 1].c = 0;
121     }
122     edge[top].c = edge[top - 1].c = 0;
123 
124     ans -= solve(t, s);
125     printf("%d", ans);
126     return 0;
127 }

AC代码

题外话：

一开始感觉跟餐巾计划问题很像，结果没想出费用流做法......

餐巾计划问题也没想出上下界做法...

太菜了。