Description
“Let the bass kick!O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA!”
LiMn2O4沉迷音乐游戏，每天都在摸鱼搓音游，而且是手机电脑两开花……为了帮助LiMn2O4尽快清醒过来，LiMn2O4答应skyer_hxx，只要skyer_hxx能写一个自动脚本来玩这个游戏，打败他的最高纪录，那么就不再摸鱼了。
这个游戏可以简化成：谱面由N个键和M条连线组成，每两个键之间有一个连线，玩家需要在键之间滑动，且连线的方向是固定的，玩家每次选择一个键，把所有从这个键出发的连线都消除掉，花费为ai，也可以将每个结束在这个点的连线消除，花费Bi。不用担心，LiMn2O4的手指足够多。最后让连线全部消失，得分就是总花费。花费越少，分数越高。
skyer_hxx何许人也，怎么会怕这点小问题？但是他现在很忙，需要你的帮助。请你对于给出的谱面，求出最小的花费。
Input
第一行有两个正整数N,M,含义同题目描述
接下来两行，第一行有N个正整数 ,代表从键i正向划到别的键需要的花费
第二行有N个正整数 ,代表从其他的键划到第i个键需要的花费
接下来M行，每一行都有两个正整数u，v，代表键u，v之间有一条u到v的连线。两个键之间可能有多个连线，同一个键之间也可能有连线。
Output
输出最小的花费，占一行。
Sample Input
3 2
1 2 1
2 1 2
1 2
1 3
Sample Output
2
题解思路：
经典的网络流最小点权覆盖问题，首先拆点，分成左右两部分，源点向所有左节点连一条边，流量为删除出边的花费。所有右节点向汇点连一条边，流量为删除入边的费用。对于每条输入给定的边<u,v>，其在左边的点为u,v，右边的点为u’,v’，那么我们连一条<u,v’>的边，流量为∞。跑一边最大流，得到的答案就是最小的费用。
首先，如果没有花费的话，这道题就是简单的最小点覆盖集。加上了点权之后，我们就要将最小割的思想融合进去。要注意费用，一定要符合S->T的顺序
代码：
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 using namespace std;
5 const int MAXN = 2010;
6 const int MAXM = 1200010;
7 const int INF = 0x3f3f3f3f;
8
9 struct Edge
10 {
11 int to, next, cap, flow;
12 } edge[MAXM];
13
14 int tol;
15 int head[MAXN];
16
17 void init()
18 {
19 tol = 2;
20 memset(head, -1, sizeof(head));
21 }
22
23 void addedge(int u, int v, int w, int rw = 0)
24 {
25 edge[tol].to = v;
26 edge[tol].cap = w;
27 edge[tol].flow = 0;
28 edge[tol].next = head[u];
29 head[u] = tol++;
30
31 edge[tol].to = u;
32 edge[tol].cap = rw;
33 edge[tol].flow = 0;
34 edge[tol].next = head[v];
35 head[v] = tol++;
36 }
37
38 int Q[MAXN];
39 int dep[MAXN], cur[MAXN], sta[MAXN];
40
41 bool bfs(int s, int t, int n)
42 {
43 int front = 0, tail = 0;
44 memset(dep, -1, sizeof(dep[0]) * (n + 1));
45 dep[s] = 0;
46 Q[tail++] = s;
47 while (front < tail)
48 {
49 int u = Q[front++];
50 for (int i = head[u]; i != -1; i = edge[i].next)
51 {
52 int v = edge[i].to;
53 if (edge[i].cap > edge[i].flow && dep[v] == -1)
54 {
55 dep[v] = dep[u] + 1;
56 if (v == t)
57 return true;
58 Q[tail++] = v;
59 }
60 }
61 }
62 return false;
63 }
64
65 int dinic(int s, int t, int n)
66 {
67 int maxflow = 0;
68 while (bfs(s, t, n))
69 {
70 for (int i = 0; i < n; i++)
71 cur[i] = head[i];
72 int u = s, tail = 0;
73 while (cur[s] != -1)
74 {
75 if (u == t)
76 {
77 int tp = INF;
78 for (int i = tail -1; i >= 0; i -- )
79 tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
80 maxflow += tp;
81 for (int i = tail - 1; i >= 0; i -- )
82 {
83 edge[sta[i]].flow += tp;
84 edge[sta[i] ^ 1].flow -= tp;
85 if (edge[sta[i]].cap - edge[sta[i]].flow == 0)
86 tail = i;
87 }
88 u = edge[sta[tail] ^ 1].to;
89 }
90 else if (cur[u] != - 1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
91 {
92 sta[tail++] = cur[u];
93 u = edge[cur[u]].to;
94 }
95 else
96 {
97 while (u != s && cur[u] == - 1)
98 u = edge[sta[ -- tail] ^ 1].to;
99 cur[u] = edge[cur[u]].next;
100 }
101 }
102 }
103 return maxflow;
104 }
105
106 int a[MAXN];
107 int b[MAXN];
108
109 int main()
110 {
111
112 int n,m;
113 scanf("%d %d",&n,&m);
114 init();
115 for(int i = 1;i<=n;i++)
116 {
117 scanf("%d",&a[i]);
118 addedge(i+n,2*n+2,a[i]);
119 }
120 for(int j = 1;j<=n;j++)
121 {
122 scanf("%d",&b[j]);
123 addedge(0,j,b[j]);
124 }
125
126 for(int i = 0;i<m;i++)
127 {
128 int u,v;
129 scanf("%d %d",&u,&v);
130 addedge(u,v+n,INF);
131 }
132 int ans = dinic(0,2*n+2,2*n+3);
133 printf("%d\n",ans);
134 return 0;
135 }
View Code