AC日记——pigs poj 1149
2024-10-20 00:40:16
思路:
最大流;
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 105
#define maxm 1005
#define maxque 200005
#define INF 0x7fffffff int n,m,val[maxm],last[maxm],head[maxn],s,t,deep[maxn];
int E[maxque],V[maxque],F[maxque],cnt=,ans,que[maxque]; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline void edge_add(int u,int v,int f)
{
E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;
} inline int min(const int &tops_,const int &tops__)
{
if(tops_<tops__) return tops_;
else return tops__;
} inline bool bfs()
{
for(int i=s;i<=t;i++) deep[i]=-;
int h=,tail=,now;que[h]=s,deep[s]=;
for(;h<tail;)
{
now=que[h++];
for(int i=head[now];i;i=E[i])
{
if(deep[V[i]]<&&F[i])
{
deep[V[i]]=deep[now]+;
if(V[i]==t) return true;
que[tail++]=V[i];
}
}
}
return false;
} inline int flowing(int now,int flow)
{
if(now==t||flow<=) return flow;
int oldflow=,pos;
for(int i=head[now];i;i=E[i])
{
if(deep[V[i]]==deep[now]+&&F[i])
{
pos=flowing(V[i],min(flow,F[i]));
flow-=pos,oldflow+=pos,F[i]-=pos,F[i^]+=pos;
if(!flow) return oldflow;
}
}
if(!oldflow) deep[now]=-;
return oldflow;
} int main()
{
in(m),in(n),t=n+;
for(int i=;i<=m;i++) in(val[i]);
for(int i=;i<=n;i++)
{
int pos=,now=,num=;in(num);
for(int j=;j<=num;j++)
{
in(pos);
if(!last[pos]) last[pos]=i,now+=val[pos];
else edge_add(last[pos],i,INF),last[pos]=i;
}
in(pos),edge_add(i,t,pos);
if(now) edge_add(s,i,now);
}
while(bfs()) ans+=flowing(s,INF);
printf("%d\n",ans);
return ;
}
最新文章
- md5 (c语言)
- AC自动机及trie图 pascal
- 我是如何来做网站优化(Seo)的?(一)
- .net中自定义过滤器对Response内容进行处理
- js中的数组Array定义与sort方法使用示例
- javascript模板引擎Mustache
- OneAlert 入门(三)——事件分析
- TinyMCE logo 可视化HTML编辑器 TinyMCE
- TF.Learn
- SeleniumServer3.0
- Python 实现双端队列 Deque
- hdu 5011(博弈)
- @Autowired和@Resource注解的一个意外重要区别
- json随笔
- [Swift]LeetCode125. 验证回文串 | Valid Palindrome
- Perl一行式:字段处理和计算
- 安利一个_Java学习笔记总结
- last individual reading task 12061183叶露婷
- apache服务器的常用功能及设置
- TCHAR用法
热门文章
- ActiveMQ使用详解---相关概念
- 并发(二)CyclicBarrier
- CKEditor的基本使用
- poj 2965 The Pilots Brothers&#39; refrigerator (dfs)
- HDU 6194 string string string(后缀数组+RMQ)
- Android中代码设置RadioButton的高端技巧
- bzoj5091 [Lydsy1711月赛]摘苹果 概率题
- Java之戳中痛点 - (1)易变业务使用脚本语言编写
- Spring学习--HelloWorld
- bootstrap再次回顾认识到的东西