[BZOJ1322]Destroying The Graph

题目大意：
有一张有向图，对于每个点，有两种操作：
1. 删掉它的所有入边
2. 删掉它的所有出边
对每个点的每个操作均有不同的价值。
求使得图上没有边的最小价值。
解题思路：
考虑把点拆成入点和出点，然后就是二分图最小点权覆盖集。
也可以考虑最小割。
从S到每个点的入点连容量为该点执行操作2的价值，每个点的出点到T连容量为该点执行操作1的价值。对于图上的每条边连容量inf的边。
然后答案就是最小割（割一条S出发的边，相当于执行了2操作，网络流不可能从该点再流向其他节点，则相当于删掉出边。操作1同理）。

C++ Code：

#include<bits/stdc++.h> using namespace std; const int S=0,T=10005,inf=0x3fffffff; struct edge{int to,nxt,cap; }e[200005]; int head[10050],cnt=1,n,m,level[10050],iter[10050]; inline void addedge(int from,int to,int flow){e[++cnt]=(edge){to,head[from],flow};head[from]=cnt;e[++cnt]=(edge){from,head[to],0};head[to]=cnt; } queue<int>q; void bfs(){level[S]=1;for(q.push(S);!q.empty();){int u=q.front();q.pop();for(int i=head[u];~i;i=e[i].nxt)if(e[i].cap&&!~level[e[i].to]){level[e[i].to]=level[u]+1;q.push(e[i].to);}} } inline int min(int a,int b){return a<b?a:b;} int dfs(int u,int f){if(!f||u==T)return f;for(int& i=iter[u];~i;i=e[i].nxt)if(e[i].cap&&level[e[i].to]>level[u]){int d=dfs(e[i].to,min(f,e[i].cap));if(d){e[i].cap-=d;e[i^1].cap+=d;return d;}else level[e[i].to]=-1;}return 0; } int dinic(){for(int flow=0,f;;){memset(level,-1,sizeof iter);if(bfs(),!~level[T])return flow;memcpy(iter,head,sizeof iter);while(f=dfs(S,inf))flow+=f;} } int main(){memset(head,-1,sizeof head);ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;++i){int p;cin>>p;addedge(i+n,T,p);}for(int i=1;i<=n;++i){int p;cin>>p;addedge(S,i,p);}while(m--){int x,y;cin>>x>>y;addedge(x,y+n,inf);}cout<<dinic()<<endl;return 0; }

 

转载于:https://www.cnblogs.com/Mrsrz/p/9304310.html

总结

以上是生活随笔为你收集整理的[BZOJ1322]Destroying The Graph的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。