做这题还是看了Amber大神的论文...
还是在这里冗余一下吧：
点覆盖集：无向图G的一个点集，使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V'∈V，满足对于所有的(u,v)∈E,都有u属于V'或v属于V'成立，即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这些边恰好组成了原边集。
最小点覆盖集： 在无向图G中，点数最小的覆盖集。
最小点权覆盖集：在带点权无向图G中，点权之和最小的点覆盖集。
通常解法：
建立源点，向X部每个点连边；建立汇点，从Y部的每个点向t连边，二分图中的边看成有向的。则任意一条从s-t的路径，一定具有s-u-v-t的形式。割的性质是不存在一条从s到t的路径。故路径上的三条边中至少有一条在割中。人为的使得(u,v)不在割中，即建立容量为INF的边(u,v)。则(s,u),(v,t)至少有一条边在最小割中，正好与点覆盖集限制条件的形式相符合。目标为求最小化点权之和，恰好也是最小割的优化模型。
怎样求割边？
割边为分割S集合与T集合的边，所以我们只需要通过DFS把能与s点连接的边都找出来，作为S集合，剩下的作为T集合中的点，则(s,u)或(v,t)这两种边的端点不在同一集合中的话，就是割边了。
#include<iostream>
#include<cstdio>
#include<string>
#define MN 222
#define INF 0x7FFFFFFF
#define CC(a) memset( a,0,sizeof(a) )
#define FF(i,N) for( int i=0;i<N;i++ )
template<class T> inline void checkmin( T &a,T b ){ if( a>b||a==-1 ) a=b; }
using namespace std;int cap[MN][MN],maze[MN][MN],gap[MN],dis[MN],cur[MN],pre[MN];
int N,M,s,t;void setG()
{CC(cap);CC(maze);s=0;t=2*N+1;for( int i=1;i<=N;i++ )scanf( "%d",&cap[i+N][t] );for( int i=1;i<=N;i++ )scanf( "%d",&cap[s][i] );int u,v;FF( i,M ){scanf( "%d%d",&u,&v );cap[u][v+N]=INF;}
}int sap()
{CC(cur),CC(gap),CC(dis);int u=pre[s]=s,maxflow=0,aug=-1;gap[0]=t+1;while( dis[s]<=t ){
loop:for( int v=cur[u];v<=t;v++ )if( (cap[u][v]-maze[u][v])>0&&dis[u]==dis[v]+1 ){pre[v]=u;cur[u]=v;checkmin( aug,cap[u][v]-maze[u][v] );u=v;if( v==t ){maxflow+=aug;for( u=pre[u];v!=s;v=u,u=pre[u] ){maze[u][v]+=aug;maze[v][u]-=aug;}aug=-1;}goto loop;}int mind=t;for( int v=0;v<=t;v++ )if( (cap[u][v]-maze[u][v])>0&&mind>dis[v] ){cur[u]=v;mind=dis[v];}if( --gap[dis[u]]==0 )break;gap[dis[u]=mind+1]++;u=pre[u];}return maxflow;
}int rec[MN],vis[MN];
void dfs( int cur )
{vis[cur]=true;for( int i=0;i<=t;i++ )if( cap[cur][i]-maze[cur][i]>0&&!vis[i] )dfs(i);
}int main()
{while( scanf("%d%d",&N,&M)!=EOF ){setG();printf( "%d\n",sap() );CC(rec),CC(vis);dfs(s);int ans=0;for( int i=1;i<=N;i++ ){if( vis[i]==0 )ans++;if( vis[i+N]==1 )ans++;}printf( "%d\n",ans );for( int i=1;i<=N;i++ ){ if( vis[i]==0 )printf( "%d -\n",i );if( vis[i+N]==1 )printf( "%d +\n",i );}}return 0;
}