思路来源：http://blog.csdn.net/lenleaves/article/details/7873441
求最小点权覆盖，同样求一个最小割，但是要求出割去了那些边，
只要用最终的剩余网络进行一次遍历就可以了，比较简单。
建图：同样是一个二分图，左边的点代表去掉出边，
右边的点代表去掉入边（小心别弄混），左边去掉出边的点与源点相连，
容量为wi- 。
然后更据给出的弧进行连线，权值为INF
使用很好理解的EK算法：（360MS）
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mm(a) memset((a),0,sizeof((a)))
#define ll long long
using namespace std; const int INF = 0x3f3f3f3f;
const int MAXN = ; queue <int> que; int vis[MAXN], res[MAXN], pre[MAXN];
int n, m, map[MAXN][MAXN];
int src, des;
stack <int> ss; bool bfs(int src, int des){
int index;
memset(pre, -, sizeof(pre));
while(!que.empty()) que.pop();
pre[src] = ;
que.push(src);
while(!que.empty()){
index = que.front();
que.pop();
for(int i = src; i <= des; ++i){
if(pre[i] == - && map[index][i] > ){
pre[i] = index;
if(i == des) return true;
que.push(i);
}
}
}
return false;
} int MaxFlow(int src, int des){
int i, maxflow = ;
while(bfs(src, des)){
int minflow = INF;
for(i = des; i != src; i = pre[i])
minflow = min(minflow, map[pre[i]][i]);
for(i = des; i != src; i = pre[i]){
map[pre[i]][i] -= minflow;
map[i][pre[i]] += minflow;
}
maxflow += minflow;
}
return maxflow;
} void init(){
mm(map);mm(vis);
} void dfs(int p){
if(vis[p]) return ;
vis[p] = true;
for(int i = src; i < des; ++i)
if(!vis[i] && map[p][i]) dfs(i);
} void solve(){
int i, x, y, ans = , temp;
init();
for(i = ; i <= n; ++i)
scanf("%d",&map[n + i][n * + ]);
for(i = ; i <= n; ++i)
scanf("%d",&map[][i]);
for(i = ; i <= m; ++i){
scanf("%d%d",&x,&y);
map[x][y + n] = INF;
} n = n << ;
src = , des = n + ;
ans = MaxFlow(src, des); dfs(); printf("%d\n",ans);
n = n >> ; for(i = ; i <= n; ++i){
if(!vis[i])
ss.push(i);
if(vis[i + n])
ss.push(i + n);
}
printf("%d\n",ss.size());
while(!ss.empty()){
temp = ss.top();
ss.pop();
if(temp <= n) printf("%d -\n",temp);
else printf("%d +\n",temp - n);
}
} int main(){
while(EOF != scanf("%d%d",&n,&m)) solve();
return ;
}
使用SAP + GAP 优化：(79MS)
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mm(a) memset((a),0,sizeof((a)))
#define ll long long
using namespace std; const int INF = 0x3f3f3f3f;
const int MAXN = ; int n, m, map[MAXN][MAXN], dis[MAXN], gap[MAXN];
int src, des;
bool vis[MAXN];
stack <int> ss; void init(){
mm(dis);mm(gap);mm(map);mm(vis);
} int sap(int u,int flow){
if(u == des) return flow;
int ans = , i, t;
for(i = ; i <= n + ; ++i)
if(map[u][i] && dis[u] == dis[i] + ){
t = sap(i, min(flow - ans, map[u][i]));
map[u][i] -= t, map[i][u] += t,ans += t;
if(ans == flow) return ans;
}
if(dis[src] >= n + ) return ans;
if(!--gap[dis[u]]) dis[src] = n + ;
++gap[++dis[u]];
return ans;
} void dfs(int p){
if(vis[p]) return ;
vis[p] = true;
for(int i = ; i < n + ; ++i)
if(!vis[i] && map[p][i]) dfs(i);
} void solve(){
int i, x, y, ans = , temp;
init();
for(i = ; i <= n; ++i)
scanf("%d",&map[n + i][n * + ]);
for(i = ; i <= n; ++i)
scanf("%d",&map[][i]);
for(i = ; i <= m; ++i){
scanf("%d%d",&x,&y);
map[x][y + n] = INF;
} n = n << ;
src = , des = n + ;
for(gap[] = n + ; dis[src] < n + ; )
ans += sap(src,INF); dfs(); printf("%d\n",ans);
n = n >> ; for(i = ; i <= n; ++i){
if(!vis[i])
ss.push(i);
if(vis[i + n])
ss.push(i + n);
}
printf("%d\n",ss.size());
while(!ss.empty()){
temp = ss.top();
ss.pop();
if(temp <= n) printf("%d -\n",temp);
else printf("%d +\n",temp - n);
}
} int main(){
while(scanf("%d%d",&n,&m)!=EOF) solve();
return ;
}