本文共 2679 字，大约阅读时间需要 8 分钟。

原题链接

题目大意

我们要删除一个有向图中的所有边，有两种删法，一是删除某点的所有入边，二是删除某点的所有出边，他们的费用不同，分别是W+和W-，我们要求一种方案，使得删除所有边的总代价最小。

思路

我们要删除某一条边<a,b>有两种删法，删除a的出边或是b的入边，我们肯定是要费用最小的那种删法，对于一个点他有两种属性，一是作为终点，二是作为起点，因此我们就想到了拆点，将一个点拆成a+和a-，分别表示a点作为终点和起点。这样建整个图也刚好就构成了一个二分图（重边和自环也不影响这种建图），左边集合全是+的点，右边集合全是-的点，如下图。并且我们要找到覆盖所有边的一个点集，就想到了最小权点覆盖集。刚好可以用最小割模型来解决二分图的最小权点覆盖集问题。

a到b的一条有向边可以从a-到b+连一条边，以此类推，将原图的所有边建成容量为正无穷的流网络，并且从s到所有+点连一条容量为W_v+的边，从所有-点到t连一条容量为W_v-的边，然后求得最小割就是答案。 然后我们要求出方案，就是所有割边上连的点。我们在残留网络中，从s出发，沿着容量大于0的边走，能走到的点就是S集合中的点，剩下的点就是T集合中的点，然后找到割边，即一个端点在S中一个端点在T中，然后我们判断这个割边的左端点是s的话就是左边+的点，如果右端点是t的话就是右边-的点，然后输出点+和点-。

代码详解

#include
   
    #include
    
     #include
     
      using namespace std;const int N = 210,M = 5210*2,INF = 0x3f3f3f3f;int n,m,s,t,cur[N],dis[N],cnt;int e[M],ne[M],w[M],h[N],idx;	//链式前向星建图bool vis[N];	//标记从s出发是否能到，标记S集合void add(int a,int b,int c) //建图模板{
   	e[idx] = b;	w[idx] = c;	ne[idx] = h[a];	h[a] = idx++;	e[idx] = a;	w[idx] = 0;	ne[idx] = h[b];	h[b] = idx++;}bool bfs()	//dinic模板{
   	queue
      
        q;	memset(dis,-1,sizeof dis);	q.push(s);	dis[s] = 0;	cur[s] = h[s];	while(q.size())	{
   		int u = q.front();		q.pop();		for(int i = h[u];~i;i = ne[i])		{
   			int v = e[i];			if(dis[v] == -1 && w[i])			{
   				dis[v] = dis[u] + 1;				cur[v] = h[v];				if(v == t)					return 1;				q.push(v);			}		}	}	return 0;}int dfs(int u,int limit){
   	if(u == t)		return limit;	int flow = 0;	for(int i = cur[u];~i;i = ne[i])	{
   		int v = e[i];		cur[u] = i;		if(dis[v] == dis[u]+1 && w[i])		{
   			int minf = dfs(v,min(w[i],limit-flow));			w[i] -= minf;			w[i^1] += minf;			flow += minf;			if(flow == limit) 				return flow;		}	}	return flow;}int dinic(){
   	int ans = 0;	while(bfs())		ans += dfs(s,INF);	return ans;}void find(int u){
   	vis[u] = 1;	for(int i = h[u];~i;i = ne[i])	{
   		int v = e[i];		if(!vis[v] && w[i])		find(v);	}}int main(){
   	cin >> n >> m;	memset(h,-1,sizeof h);	s = 0,t = n+n+1;	for(int i = 1;i <= n;i++)	{
   		int w;		cin >> w;		add(s,i,w);	//建s到+点的边	}	for(int i = 1;i <= n;i++)	{
   		int w;		cin >> w;		add(n+i,t,w);	//建-点到t的边	}	while(m--)	{
   		int a,b;		cin >> a >> b;		add(b,n+a,INF);		//二分图内部的边容量建成正无穷	}	cout << dinic() << endl;	//最小割就是最小权	 	find(s);	//从s出发标记S集合	for(int i = 0;i < idx;i += 2)	//枚举所有正向边	{
   		int a = e[i^1],b = e[i];	//a是起点，b是终点		if(vis[a] && !vis[b])		//如果起点在S集合且终点在T集合说明该边是割边			cnt++;			//数量+1	}	cout << cnt << endl;	for(int i = 0;i < idx;i += 2)	{
   		int a = e[i^1],b = e[i];		if(vis[a] && !vis[b])			if(a == s)		//该边是割边且起点是s，说明是+点				cout << b << " +" << endl;	}	for(int i = 0;i < idx;i += 2)	{
   		int a = e[i^1],b = e[i];		if(vis[a] && !vis[b])			if(b == t)		//该边是割边且终点是t，说明是-点				cout << a-n << " -" << endl;	}	 	return 0;}
      
     
    
   

转载地址：http://kbbki.baihongyu.com/