2019HDU多校赛第二场 H HDU 6598 Harmonious Army(最小割模型)

﹏ヽ暗。殇╰゛Y 2021-11-10 15:24 212阅读 0赞

参考博客https://blog.csdn.net/u013534123/article/details/97142191

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+50; int S,T,From[maxn],Laxt[maxn],Next[maxn],To[maxn]; ll Cap[maxn],cnt; int vd[maxn],dis[maxn]; void add(int u,int v,ll c){ Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;Cap[cnt]=c;From[cnt]=u; Next[++cnt]=Laxt[v];Laxt[v]=cnt;To[cnt]=u;Cap[cnt]=0;From[cnt]=v; } ll sap(int u,ll flow,int limit){ if(u==T||flow==0)return flow; ll tmp,delta=0; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[u]==dis[v]+1&&Cap[i]){ tmp=sap(v,min(flow-delta,Cap[i]),limit); Cap[i]-=tmp;Cap[i^1]+=tmp;delta+=tmp; if(dis[S]>=limit||delta==flow)return delta; } } vd[dis[u]]--;if(!vd[dis[u]])dis[S]=limit; vd[++dis[u]]++; return delta; } void init(int limit){ cnt=1; for(int i=0;i<=limit;i++)Laxt[i]=dis[i]=vd[i]=0; } int main(){ std::ios::sync_with_stdio(false); int n,m; while(cin>>n>>m){ init(n+2); S=0,T=n+1; ll ans=0; for(int i=1;i<=m;i++){ ll u,v,a,b,c; cin>>u>>v>>a>>b>>c; ans+=(a+b+c)*2; add(u,T,a/4+4*c/3); add(v,T,a/4+4*c/3); add(S,u,5*a/4+c/3); add(S,v,5*a/4+c/3); add(u,v,c/3+a/2); add(v,u,c/3+a/2); } ll pp=0; while(dis[S]<n+2){ pp+=sap(S,1e9,n+2); } cout<<(ans-pp)/2<<endl; } return 0; }

转载于:https://www.cnblogs.com/luowentao/p/11253554.html

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019hdu第二场

10：签到求n!取模 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] include <iostream>

￡神魔★判官ぃ/ 2023年10月11日 09:16/ 0 赞/ 8 阅读

相关 2018HDU多校联赛第二场

题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=6318][http_acm.hdu.edu.cn_showproblem.p

今天药忘吃喽~/ 2022年05月19日 14:00/ 0 赞/ 206 阅读

相关 2018HDU多校第二场——1003 Cover

题目链接：[hdu6311][] 题目大意：开始读题时，想到了多少次dfs可以遍历完所有边，就是答案。却没有想到利用添加虚边，进行欧拉路的一个查找，然后再把添加的虚边去掉，剩

你的名字/ 2022年05月18日 01:39/ 0 赞/ 171 阅读

相关 2019HDU多校第一场 1009 String

Problem Description Tom has a string containing only lowercase letters. He wants to cho

傷城~/ 2021年11月27日 00:44/ 0 赞/ 298 阅读

相关 HDU 6581 Vacation——————2019多校第一场，思维

[Vacation][] Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (J

谁借莪１个温暖的怀抱￠/ 2021年11月26日 21:42/ 0 赞/ 276 阅读

相关 2019HDU多校赛第二场 H HDU 6598 Harmonious Army(最小割模型)

参考博客https://blog.csdn.net/u013534123/article/details/97142191 include<bits/stdc++.h

﹏ヽ暗。殇╰゛Y/ 2021年11月10日 15:24/ 0 赞/ 213 阅读

相关 [2019HDU多校第一场][HDU 6578][A. Blank]

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6578][http_acm.hdu.edu.cn_showproblem.ph

本是古典何须时尚/ 2021年11月01日 06:10/ 0 赞/ 281 阅读

相关 [2019HDU多校第一场][HDU 6584][G. Meteor]

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6584][http_acm.hdu.edu.cn_showproblem.ph

柔情只为你懂/ 2021年11月01日 06:10/ 0 赞/ 351 阅读

相关 [2019HDU多校第一场][HDU 6580][C. Milk]

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6580][http_acm.hdu.edu.cn_showproblem.ph

你的名字/ 2021年10月18日 07:31/ 0 赞/ 310 阅读

相关 HDU6598 Harmonious Army

经典网络流模型，可以看一下论文（浅析一类最小割问题(pty)） ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

红太狼/ 2021年09月30日 05:24/ 0 赞/ 200 阅读