题目分析：最小割。因为每次删除的是一个点的所有入边或者所有出边。那么就很明显了，拆点，将i拆成i和I+n2个点，分别表示第i个点的入度点和出度点。源点到每个i连边，表示从i点的出边，边权为outi，i+n表示第i个点的入度点，那么i+n-->汇点建边，边权为ini，对于每对给定的有向边i->j，建边i->j + n，边权为无穷大。原理其实和这题是十分类似的。因为要求一个最小割，要保证源点和汇点被分在2个集合中，i->j + n边权无穷大后，保证割边集不可能包含i->j + n这类边，那么割边集只能包含s->i和j + n->t，这样就保证求出的最小割将源点和汇点分开。建好图跑一遍最大流即可。
不过这题还要给一个最小割的方案，输出割点。搞了好久。。。
其实也不是很复杂，对求完最大流的残余网络进行一次dfs即可。从源点开始dfs，只对边权残余容量为0的边遍历。所有遍历到的点标记上。然后检查1-2n的所有点，分2类：
1：i<=n的点，根据前面建图可知，这类点是表示第i个点的出边的，如果从源点无法通过残余容量为0的边遍历到，那么说明这个点的出边是属于割集的，即所求点。反之，对于能遍历到的点，肯定不是割点。
2：i>n的点，这类点是表示第i个点的入边，如果被遍历到了，肯定是属于割点的。为什么呢，因为从源点开始遍历，肯定要先通过1-n的点到达n+1~n + n的点，假设到达了i+n这个点，并且假设是从j到达i+n的点的，前面已经说了，j肯定不属于割点，那么j的出边肯定就没有删除，要求要删掉所有的边，既然从j不能删掉从j出发的边，那么只能删掉j所到达的边的入边了。既然能从j->i+n，那么j->i肯定右边，相对i来说，这是条入边，i一定要属于割点才能保证删掉所有的边。
详情请见代码：
#include#include #include #include using namespace std; const int N = 105; const int M = 10005; const int inf = 0x3f3f3f3f; int m,n,num; struct node { int to,c,f,next,pre; }arc[M]; int head[N],que[N],sta[N],cnt[N],dis[N],rpath[N]; bool flag[N][N]; void build(int s,int e,int cap) { arc[num].to = e; arc[num].c = cap; arc[num].f = 0; arc[num].next = head[s]; head[s] = num ++; arc[num - 1].pre = num; arc[num].pre = num - 1; arc[num].to = s; arc[num].c = arc[num].f = 0; arc[num].next = head[e]; head[e] = num ++; } void init() { memset(head,-1,sizeof(head)); memset(flag,false,sizeof(flag)); num = 0; int i,a,b,d; scanf("%d",&m); for(i = 1;i <= n;i ++) { scanf("%d",&d); build(i + n,n + n + 1,d); } for(i = 1;i <= n;i ++) { scanf("%d",&d); build(0,i,d); } while(m --) { scanf("%d%d",&a,&b); if(flag[a][b + n]) continue; flag[a][b + n] = true; build(a,b + n,inf); } } void re_Bfs() { int i,front,rear; for(i = 0;i <= n + n + 1;i ++) { dis[i] = n + n + 2; cnt[i] = 0; } front = rear = 0; dis[n + n + 1] = 0; cnt[0] = 1; que[rear ++] = n + n + 1; while(front != rear) { int u = que[front ++]; for(i = head[u];i != -1;i = arc[i].next) { if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < n + n + 2) continue; dis[arc[i].to] = dis[u] + 1; cnt[dis[arc[i].to]] ++; que[rear ++] = arc[i].to; } } } void dfs(int u) { if(cnt[u]) return; cnt[u] = 1; for(int i = head[u];i != -1;i = arc[i].next) if(arc[i].c > 0 && cnt[arc[i].to] == 0) dfs(arc[i].to); } void show(int maxflow) { memset(cnt,0,sizeof(cnt)); dfs(0); int i,rear = 0; for(i = 1;i <= n;i ++) { if(cnt[i] == 0) que[rear ++] = i; if(cnt[i + n]) que[rear ++] = i + n; } printf("%d\n",rear); for(i = 0;i < rear;i ++) { if(que[i] <= n) printf("%d -\n",que[i]); else printf("%d +\n",que[i] - n); } } void ISAP() { re_Bfs(); int i,u,maxflow = 0; for(i = 0;i <= n + n + 1;i ++) sta[i] = head[i]; u = 0; while(dis[0] < n + n + 2) { if(u == n + n + 1) { int curflow = inf; for(i = 0;i != n + n + 1;i = arc[sta[i]].to) curflow = min(curflow,arc[sta[i]].c); for(i = 0;i != n + n + 1;i = arc[sta[i]].to) { arc[sta[i]].c -= curflow; arc[sta[i]].f += curflow; arc[arc[sta[i]].pre].c += curflow; arc[arc[sta[i]].pre].f -= curflow; } maxflow += curflow; u = 0; } for(i = sta[u];i != -1;i = arc[i].next) if(arc[i].c > 0 && dis[u] == dis[arc[i].to] + 1) break; if(i != -1) { sta[u] = i; rpath[arc[i].to] = arc[i].pre; u = arc[i].to; } else { if((-- cnt[dis[u]]) == 0) break; int Min = n + n + 2; sta[u] = head[u]; for(i = sta[u];i != -1;i = arc[i].next) if(arc[i].c > 0) Min = min(Min,dis[arc[i].to]); dis[u] = Min + 1; cnt[dis[u]] ++; if(u != 0) u = arc[rpath[u]].to; } } printf("%d\n",maxflow); show(maxflow); } int main() { while(scanf("%d",&n) != EOF) { init(); ISAP(); } return 0; } //1380K 63MS /* 3 6 1 2 3 4 2 1 1 2 1 1 3 2 1 2 3 1 2 3 3 5 1 2 3 4 2 1 1 2 3 2 1 2 3 1 2 3 */