题目链接:
poj2125
题意:
给出一张N个顶点M条边的有向图。
对于每个顶点x,有两种操作：
1,删除所有进入x的边,花费为a;
2.删除所有从x出去的边,花费为b.
问把图中所有边删除所需要的最小花费.并输出对应的操作。
解题思路：
由题目条件(删除入边,删除出边)首先想到应该是拆点. 这样题目的问题转化为最小点权覆盖问题.即用最少（花费）的顶点覆盖所有边
对于这个问题,我们可以用网络流中的最小割解决,方法如下:
源点连接拆后的出点,容量为b
汇点连接拆后的入点,容量为a
已有边容量为无穷大。
对于输出割点:
从起点dfs通过未饱和弧标记所有点。
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 <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#define maxn 305const int MAXN =305;const int MAXM=40020;const int INF=0x3f3f3f3f;using namespace std;struct Edge {int to,cap,flow,next;} edge[MAXM];int head[MAXN],tot,gap[MAXN],d[MAXN],cur[MAXN],que[MAXN],p[MAXN];void init(){tot=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int c){edge[tot]=(Edge){v,c,0,head[u]};head[u] = tot++;edge[tot]=(Edge){u,c,c,head[v]};head[v] = tot++;}int isap(int source,int sink,int N){memset(gap,0,sizeof(gap));memset(d,0,sizeof(d));memcpy(cur,head,sizeof(head));int top = 0,x = source,flow = 0;while(d[source] < N) {if(x == sink) {int Min = INF,inser=0;for(int i = 0; i < top; ++i) {if(Min > edge[p[i]].cap – edge[p[i]].flow) {Min = edge[p[i]].cap – edge[p[i]].flow;inser = i;}}for(int i = 0; i < top; ++i) {edge[p[i]].flow += Min;edge[p[i]^1].flow -= Min;}if(Min!=INF) flow += Min;top = inser;x = edge[p[top]^1].to;continue;}int ok = 0;for(int i = cur[x]; i != -1; i = edge[i].next) {int v = edge[i].to;if(edge[i].cap > edge[i].flow && d[v]+1 == d[x]) {ok = 1;cur[x] = i;p[top++] = i;x = edge[i].to;break;}}if(!ok) {int Min = N;for(int i = head[x]; i != -1; i = edge[i].next) {if(edge[i].cap > edge[i].flow && d[edge[i].to] < Min) {Min = d[edge[i].to];cur[x] = i;}}if(–gap[d[x]] == 0) break;gap[d[x] = Min+1]++;if(x != source) x = edge[p[–top]^1].to;}}return flow;}int vis[maxn];void dfs(int u){vis[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(edge[i].flow<edge[i].cap&&!vis[v])dfs(v);}}int main(){// freopen("in.txt","r",stdin);int n,m,a,b;int s,t;vector<int>ans;while(~scanf("%d%d",&n,&m)){s=0,t=2*n+1;init();for(int i=1;i<=n;i++){scanf("%d",&a);addedge(i+n,t,a);}for(int j=1;j<=n;j++){scanf("%d",&a);addedge(s,j,a);}while(m–){scanf("%d%d",&a,&b);addedge(a,b+n,INF);}printf("%d\n",isap(s,t,t+1));memset(vis,0,sizeof(vis));ans.clear();dfs(s);for(int i=1;i<=n;i++){if(!vis[i])ans.push_back(i);if(vis[i+n])ans.push_back(i+n);}printf("%d\n",ans.size());for(int i=0;i<ans.size();i++){if(ans[i]<=n)printf("%d -\n",ans[i]);elseprintf("%d +\n",ans[i]-n);}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
理想的路总是为有信心的人预备着
