首页 > 代码库 > 【BZOJ2039】【2009国家集训队】employ人员雇佣 最小割
【BZOJ2039】【2009国家集训队】employ人员雇佣 最小割
转载请注明出处:http://blog.csdn.net/vmurder/article/details/42651751
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。
最小割心得:
首先需要一定的功底来发现这道题是最小割,并且投入思考。
然后想怎么建图:
最小割都是先算上所有收益,然后再通过网络图进行割边减去部分权值。
收益有时候可能带上负值。
然后我们需要思考什么能带来权值,什么会有权值冲突。
而最小割图一般都是拆成S集和T集考虑,即取与不取,某人/点选A或者选B等等,
这样就会带来冲突,也就是需要割的边。
然后我们需要把所有权值的得与失列出来,针对性建图,然后check几种情况:
比如两个人都在S集、都在T集,甲S乙T,甲T乙S等等,我们看这样会割掉哪些边,失去哪些权值。
如果发现建错了,也可以有针对性地进行修改。
就说这么多吧。
下面说这道题的建图:
点:每个人一个点,额外设源汇点。
边:
源向人连这个人能造成的全部收益(当作雇佣所有人,然后此人造成的收益)
人与人之间连两人熟悉度*2,呃,题意问题。
人向汇连雇佣需要花的钱。
分析一下
一个人雇与不雇造成的收益/损失,
两个人都雇、都不雇、雇一个造成的损失,
就很容易明白这个建图了。
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1005 #define M 2001000 #define LL long long #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3fLL using namespace std; struct KSD { int v,next; long long len; }e[M]; int head[N],cnt; inline void add(int u,int v,long long len) { e[++cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } int s,t,d[N]; queue<int>q; bool bfs() { memset(d,0,sizeof(d)); while(!q.empty())q.pop(); int i,u,v; q.push(s),d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next) { if(!d[v=e[i].v]&&e[i].len) { d[v]=d[u]+1; if(v==t)return 1; q.push(v); } } } return 0; } long long dinic(int x,long long flow) { if(x==t)return flow; long long remain=flow,k; int i,v; for(i=head[x];i&&remain;i=e[i].next) { if(d[v=e[i].v]==d[x]+1&&e[i].len) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i].len-=k,e[i^1].len+=k; remain-=k; } } return flow-remain; } int n; long long cost[N],map[N][N],sum[N]; long long res,maxflow; void build() { int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%lld",&cost[i]); for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%lld",&map[i][j]),sum[i]+=map[i][j]; cnt=1,s=n+1,t=n+2; for(i=1;i<=n;i++)add(s,i,sum[i]),add(i,s,0),res+=sum[i]; for(i=1;i<=n;i++)add(i,t,cost[i]),add(t,i,0); for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)add(i,j,2*map[i][j]),add(j,i,2*map[i][j]); } int main() { // freopen("test.in","r",stdin); build(); while(bfs())maxflow+=dinic(s,inf); printf("%d\n",res-maxflow); return 0; }
【BZOJ2039】【2009国家集训队】employ人员雇佣 最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。