构图思路:
1.将所有顶点v拆成两个点， v1,v2
2.源点S与v1连边，容量为 W-
3.v2与汇点连边，容量为 W+
4.对图中原边( a, b ), 连边 (a1,b2)，容量为正无穷大
则该图的最小割(最大流)即为最小花费。
简单证明： 根据ST割集的定义，将顶点分成两个点集。所以对于原图中的边(a,b),转换成 S->a1->b2->T. 则此时路径必定存在
一条割边，因为a1->b2为无穷大，所以割边必定是 S->a1 or b2->T, 若为前者则意味着删除a顶点的W-，后者则是b顶点的W+.
所以该图最小割即为最小花费。
计算方案： 对于构图后跑一次最大流，然后对于残留网络进行处理，首先从源点S出发，标记所有能访问到的顶点，这些顶点即为S割点集中
的顶点。 其他则为T集合中顶点， 然后从所有边中筛选出( A属于S,B属于T,且（A,B)容量为0 )的边，即为割边。因为我们的W+/W-边都只有一条，
且都分开了。比较容易处理。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <string>
7 #include <vector>
8 #include <set>
9 #include <map>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 typedef long long LL;
16 const int INF = 0x4fffffff;
17 const double EXP = 1e-5;
18 const int MS = 2005;
19 const int SIZE = 100005;
20
21 struct edge
22 {
23 int v,c,f,other;
24 }e;
25
26 vector<edge> edges[MS]; // 邻接表
27 vector<int> level_edges[MS];
28 vector<int> ans;
29
30 int que[MS],level[MS],pre[MS],hash[MS],d[MS];
31 int s,t;
32
33 void add(int u,int v,int c)
34 {
35 e.v=v;
36 e.c=c;
37 e.f=0;
38 e.other=edges[v].size();
39 edges[u].push_back(e);
40
41 e.v=u; // reverse edge
42 e.c=0;
43 e.f=0;
44 e.other=edges[u].size()-1;
45 edges[v].push_back(e);
46 }
47
48 bool BFS() // bfs 构建层次网络
49 {
50 int head=0,tail=0,cur,i;
51 for(int i=s;i<=t;i++)
52 level_edges[i].clear();
53 memset(level,0xff,sizeof(level));
54 que[tail++]=s;
55 level[s]=0;
56 while(head<tail)
57 {
58 cur=que[head++];
59 for(i=0;i<edges[cur].size();i++)
60 {
61 e=edges[cur][i];
62 if(e.c>e.f)
63 {
64 if(level[e.v]==-1)
65 {
66 que[tail++]=e.v;
67 level[e.v]=level[cur]+1;
68 }
69 if(level[e.v]==level[cur]+1)
70 {
71 level_edges[cur].push_back(i);
72 }
73 }
74 }
75 }
76 if(level[t]!=-1)
77 return 1;
78 else
79 return 0;
80 }
81
82
83 int dinic()
84 {
85 int i,j,ans=0,len;
86 while(BFS())
87 {
88 memset(hash,0,sizeof(hash));
89 while(!hash[s])
90 {
91 d[s]=INF;
92 pre[s]=-1;
93 for(i=s;i!=t&&i!=-1;i=j)
94 {
95 len=level_edges[i].size();
96 while(len&&hash[ edges[i][level_edges[i][len-1]].v] )
97 {
98 level_edges[i].pop_back();
99 len--;
100 }
101 if(!len)
102 {
103 hash[i]=1;
104 j=pre[i];
105 continue;
106 }
107 j=edges[i][level_edges[i][len-1]].v;
108 pre[j]=i;
109 d[j]=min(d[i],edges[i][level_edges[i][len-1]].c-edges[i][level_edges[i][len-1]].f);
110 }
111 if(i==t)
112 {
113 ans+=d[t];
114 while(i!=s)
115 {
116 j=pre[i];
117 len=level_edges[j][level_edges[j].size()-1];
118 edges[j][len].f+=d[t];
119 if(edges[j][len].f==edges[j][len].c)
120 level_edges[j].pop_back();
121 edges[i][edges[j][len].other].f-=d[t];
122 i=j;
123 }
124 }
125 }
126 }
127 return ans;
128 }
129
130 void DFS(int u)
131 {
132 int i,k;
133 hash[u]=1;
134 for(i=0;i<edges[u].size();i++)
135 {
136 k=edges[u][i].v;
137 if(!hash[k]&&edges[u][i].c-edges[u][i].f>0)
138 DFS(k);
139 }
140 }
141
142 int main()
143 {
144 int n,m,i,j,k,N,tmp,answer;
145 while(scanf("%d%d",&n,&m)!=EOF)
146 {
147 N=2*n+1;
148 s=0;
149 t=N;
150 for(i=s;i<=t;i++)
151 edges[i].clear();
152 for(i=1;i<=n;i++)
153 {
154 scanf("%d",&tmp);
155 add(n+i,N,tmp);
156 }
157 for(i=1;i<=n;i++)
158 {
159 scanf("%d",&tmp);
160 add(0,i,tmp);
161 }
162 for(k=0;k<m;k++)
163 {
164 scanf("%d%d",&i,&j);
165 add(i,n+j,INF);
166 }
167 answer=dinic();
168 memset(hash,0,sizeof(hash));
169 DFS(0);
170 ans.clear();
171 for(i=1;i<=n;i++)
172 {
173 if(!hash[i])
174 ans.push_back(i);
175 if(hash[n+i])
176 ans.push_back(n+i);
177 }
178 printf("%d\n%d\n",answer,ans.size());
179 for(i=0;i<ans.size();i++)
180 {
181 if(ans[i]<=n)
182 printf("%d -\n",ans[i]);
183 else
184 printf("%d +\n",ans[i]-n);
185 }
186 }
187 return 0;
188 }