3438: 小M的作物

题目:传送门

题解:

   最小割标准水题(做了几天的最小割之后表示是真的水)

   为什么水:博主已经做过两道基本一样的题目了...

   详情参考:bzoj3894

代码:

 

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define N 510000
#define inf 999999999
#define qread(x)x=read();
using namespace std;
typedef long long LL;
inline LL read()
{
LL f=,x=;char ch;
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
struct node
{
int x,y,next,other;
LL c;
}a[N*];int len,last[N];
LL n,m,st,ed,head,tail;
void ins(int x,int y,LL c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int list[N],h[N];
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c>)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed]>)return true;
return false;
}
int find_flow(int x,LL flow)
{
if(x==ed)return flow;
LL s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c> && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
LL A[],B[],c1[],c2[];
int main()
{
len=;memset(last,,sizeof(last));
qread(n);
LL sum=;
for(int i=;i<=n;i++){qread(A[i]);sum+=A[i];}
for(int i=;i<=n;i++){qread(B[i]);sum+=B[i];}
qread(m);st=N-;ed=N-;
for(int i=;i<=n;i++)
{
ins(st,i,A[i]);
ins(i,ed,B[i]);
}
for(int i=;i<=m;i++)
{
int k;qread(k);qread(c1[i]);qread(c2[i]);
sum+=c1[i]+c2[i];ins(st,i+n,c1[i]);ins(i+n+m,ed,c2[i]);
for(int j=;j<=k;j++)
{
int x;qread(x);
ins(i+n,x,inf);
ins(x,i+n+m,inf);
}
}
LL ans=;
while(bt_h())ans+=find_flow(st,inf);
printf("%lld\n",sum-ans);
return ;
}

最新文章

  1. xamarin真的是一个鸡肋吗?
  2. Unity WebGL MoonSharp崩溃问题
  3. Play1+angularjs+bootstrap ++ (idea + livereload)
  4. unity5.0新功能-布料、动画系统
  5. cookie和浏览器
  6. three.js运动
  7. (转)UIColor 的使用
  8. php中文编码
  9. 《Velocity java开发指南》中文版(上)转载
  10. WordPress BackWPup插件‘tab’参数跨站脚本漏洞
  11. unity3d游戏开发猜想——当程序猿老去
  12. 图像编程学习笔记2——bmp位图平移
  13. vue的一些坑(第一天)
  14. Asp.Net Core 轻松学-一行代码搞定文件上传
  15. 论文阅读笔记(七)YOLO
  16. ubuntu 下安装docker 踩坑记录
  17. 从零开始学习PYTHON3讲义(八)列表类型跟冒泡排序
  18. vue评论显示隐藏,JavaScript显示关闭
  19. python等值和大小比较
  20. traceroute命令初探

热门文章

  1. 第八章 Servlet概述
  2. ASP.NET-使用json
  3. VC6.0VB6.0 Scratch等软件
  4. bzoj 1600 &amp;amp; Usaco 月赛 2008 建造栅栏 题解
  5. SEO分享:关于SEO的十个问题
  6. zzuoj--10399--Turing equation(模拟)
  7. Redis常用命令速查 &lt;第二篇&gt;【转】
  8. SpringCloud学习笔记(8)----Spring Cloud Netflix之负载均衡-Ribbon的负载均衡的策略
  9. BZOJ 2154/2693 Crash的数字表格/jzptab (莫比乌斯反演)
  10. nginx开启gzip压缩后导致apk包下载不能正常安装