Magic Potion(网络流)

　　2018南京的铜牌题，听说学长他们上来就A了，我这个图论选手也就上手做了做，结果一言难尽......

　　发此篇博客希望自己能牢记自己的菜...

　　本题大意：有n个heros和m个monsters大战，每个heros只能杀一个monsters且他们只能杀固定编号的monsters，现在有药水k瓶，如果英雄喝了药水那么它又可以多杀一个怪兽，每个英雄最多能喝一瓶药水。现在给你n， m， k，还有n个英雄各自能击杀怪兽的编号，问这些英雄最多能杀多少怪兽。

　　题解太水，大佬请绕道。。。

　　这里我们将英雄初始情况下能杀一个人定义为英雄的初始能量。

　　我用的网络流，别的都是正常思路，唯一一点就是，药水这个点，我们可以考虑从超级源点起向另一个源点引一条容量为k的边，从这个源点向英雄连一条容量为1的边表示药水。

　　千万不要像傻逼的我。。。

　　下面介绍一下我的做法。。。超级源点给附加源点提供药水，然后附加源点给英雄，英雄有一个初始能量？哦好了那我们把英雄拆点成a1, a2，给他a2一个能量就可以了，然后让a2代替英雄做该做的事，具体做法是附加源点给a1药水，a1自己本来有一个能量然后还可以接收药水(起始流量为1，容量为2)，a2去打怪兽，然后向超级汇点统计。。。。。。

　　总的来说我的做法就可以描述为，正解的初始能量是超级源点给的，这本来也是常规思路，我个杠精非得拆点让他兄弟给，至今不明白为什么错了，堪忧。

　　哦对了，样例都没过一直感觉自己毫无问题，输出中间状态发现药水给出去了但是英雄连自己的初始能量都没用掉。。。

　　恨自己为什么不常规思路。。。奇葩

　　下面是正解代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 1000 + 5, maxm = maxn * maxn * 2, inf = 0x3f3f3f3f;
 7 
 8 struct Edge {
 9     int to, cap, flow, next, from;
10 } edge[maxm << 1];
11 
12 int tot, head[maxn << 1], que[maxn << 1], dep[maxn << 1], cur[maxn << 1], sta[maxn << 1];
13 
14 void init() {
15     tot = 2;
16     memset(head, -1, sizeof head);
17 }
18 
19 
20 void addedge(int u, int v, int cap) {
21     edge[tot].to = v; edge[tot].cap = cap; edge[tot].flow = 0; edge[tot].from = u;
22     edge[tot].next = head[u]; head[u] = tot ++;
23     edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0; edge[tot].from = v;
24     edge[tot].next = head[v]; head[v] = tot ++;
25 }
26 
27 bool bfs(int s, int t, int n) {
28     memset(dep, -1, sizeof dep[0] * (n + 1));
29     int front = 0, tail = 0;
30     dep[s] = 0;
31     que[tail ++] = s;
32     while(front < tail) {
33         int u = que[front ++];
34         for(int i = head[u]; ~i; i = edge[i].next) {
35             int v = edge[i].to;
36             if(edge[i].cap > edge[i].flow && dep[v] == -1) {
37                 dep[v] = dep[u] + 1;
38                 if(v == t) return true;
39                 que[tail ++] = v;
40             }
41         }
42     }
43     return false;
44 }
45 
46 int dinic(int s, int t, int n) {
47     int maxflow = 0;
48     while(bfs(s, t, n)) {
49         for(int i = 0; i <= n; i ++) cur[i] = head[i];
50         int u = s, tail = 0;
51         while(~cur[s]) {
52             if(u == t) {
53                 int tp = inf;
54                 for(int i = tail - 1; i >= 0; i --)
55                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
56                 maxflow += tp;
57                 for(int i = tail - 1; i >= 0; i --) {
58                     edge[sta[i]].flow += tp;
59                     edge[sta[i] ^ 1].flow -= tp;
60                     if(edge[sta[i]].cap - edge[sta[i]].flow == 0)   tail = i;
61                 }
62                 u = edge[sta[tail] ^ 1].to;
63             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
64                 sta[tail ++] = cur[u];
65                 u = edge[cur[u]].to;
66             } else {
67                 while(u != s && cur[u] == -1)
68                     u = edge[sta[-- tail] ^ 1].to;
69                 cur[u] = edge[cur[u]].next;
70             }
71         }
72     }
73     return maxflow;
74 }
75 
76 int main() {
77     int s1, s2, t;
78     int n, m, k;
79     int num, v;
80     init();
81     scanf("%d %d %d", &n, &m, &k);
82     s1 = n + m + 1, s2 = s1 + 1, t = s2 + 1;
83     addedge(s1, s2, k);
84     for(int u = 1; u <= n; u ++) {
85         addedge(s2, u, 1);
86         addedge(s1, u, 1);
87         scanf("%d", &num);
88         while(num --) {
89             scanf("%d", &v);
90             addedge(u, n + v, 1);
91         }
92     }
93     for(int i = 1; i <= m; i ++) {
94         addedge(n + i, t, 1);
95     }
96     printf("%d
", dinic(s1, t, n + m + 3));
97     return 0;
98 }

　　下面是样例都没过的代码？？？

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 const int maxn = 1000 + 5, maxm = maxn * maxn * 2, inf = 0x3f3f3f3f;
  7 
  8 struct Edge {
  9     int to, cap, flow, next, from;
 10 } edge[maxm << 1];
 11 
 12 int tot, head[maxn << 1], que[maxn << 1], dep[maxn << 1], cur[maxn << 1], sta[maxn << 1];
 13 
 14 void init() {
 15     tot = 2;
 16     memset(head, -1, sizeof head);
 17 }
 18 
 19 
 20 void addedge(int u, int v, int flow, int cap) {
 21     edge[tot].to = v; edge[tot].cap = cap; edge[tot].flow = flow; edge[tot].from = u;
 22     edge[tot].next = head[u]; head[u] = tot ++;
 23     edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0; edge[tot].from = v;
 24     edge[tot].next = head[v]; head[v] = tot ++;
 25 }
 26 
 27 bool bfs(int s, int t, int n) {
 28     memset(dep, -1, sizeof dep[0] * (n + 1));
 29     int front = 0, tail = 0;
 30     dep[s] = 0;
 31     que[tail ++] = s;
 32     while(front < tail) {
 33         int u = que[front ++];
 34         for(int i = head[u]; ~i; i = edge[i].next) {
 35             int v = edge[i].to;
 36             if(edge[i].cap > edge[i].flow && dep[v] == -1) {
 37                 dep[v] = dep[u] + 1;
 38                 if(v == t) return true;
 39                 que[tail ++] = v;
 40             }
 41         }
 42     }
 43     return false;
 44 }
 45 
 46 int dinic(int s, int t, int n) {
 47     int maxflow = 0;
 48     while(bfs(s, t, n)) {
 49         for(int i = 0; i <= n; i ++) cur[i] = head[i];
 50         int u = s, tail = 0;
 51         while(~cur[s]) {
 52             if(u == t) {
 53                 int tp = inf;
 54                 for(int i = tail - 1; i >= 0; i --)
 55                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
 56                 maxflow += tp;
 57                 for(int i = tail - 1; i >= 0; i --) {
 58                     edge[sta[i]].flow += tp;
 59                     edge[sta[i] ^ 1].flow -= tp;
 60                     if(edge[sta[i]].cap - edge[sta[i]].flow == 0)   tail = i;
 61                 }
 62                 u = edge[sta[tail] ^ 1].to;
 63             } else if(~ cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
 64                 sta[tail ++] = cur[u];
 65                 u = edge[cur[u]].to;
 66             } else {
 67                 while(u != s && cur[u] == -1)
 68                     u = edge[sta[-- tail] ^ 1].to;
 69                 cur[u] = edge[cur[u]].next;
 70             }
 71         }
 72     }
 73     return maxflow;
 74 }
 75 
 76 int main() {
 77     int s1, s2, t;
 78     int n, m, k;
 79     int num, v;
 80     init();
 81     scanf("%d %d %d", &n, &m, &k);
 82     s1 = 2 * n + m + 1, s2 = s1 + 1, t = s2 + 1;
 83     addedge(s1, s2, 0, k);
 84     for(int u = 1; u <= n; u ++) {
 85         addedge(s2, u, 0, 1);//
 86         addedge(u, u + n, 1, 2);
 87         scanf("%d", &num);
 88         while(num --) {
 89             scanf("%d", &v);
 90             addedge(u + n, 2 * n + v, 0, 1);//
 91         }
 92     }
 93     for(int i = 1; i <= m; i ++) {
 94         addedge(2 * n + i, t, 0, 1);//
 95     }
 96     printf("%d
", dinic(s1, t, 2 * n + m + 3));
 97     for(int i = 2; i <= tot; i ++) {
 98         if(edge[i].flow > 0 && !(i & 1)) {
 99             printf("%d %d %d
", edge[i].from, edge[i].to, edge[i].flow);
100         }
101     }
102     return 0;
103 }

甚至现在还认为自己是对的...