bzoj状态里有两种,一种时间是个位数,一种是四位数,我就是四位数的那种,,,估计都是看了hzwer..

 #include <bits/stdc++.h>

 #define    INF    0x3f3f3f3f

 using namespace std;

 template<const int _n,const int _m>
struct Edge
{
struct Edge_base { int to,next,w; }e[_m]; int cnt,p[_n];
Edge() { clear(); }
void insert(const int x,const int y,const int z)
{ e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }
int start(const int x) { return p[x]; }
void clear() { cnt=;memset(p,,sizeof(p)); }
void Link(const int x,const int y,const int z)
{ insert(x,y,z); insert(y,x,); }
Edge_base& operator[](const int x) { return e[x]; }
}; Edge<,>e;
int n,cnt,Flow,level[];
int SS,SSS,TTT,cur[],In[]; bool Bfs(const int S)
{
int i,t;
queue<int> Q;
memset(level,,sizeof(level));
level[S]=;
Q.push(S);
while(!Q.empty())
{
t=Q.front();Q.pop();
for(i=e.start(t);i;i=e[i].next)
{
if(!level[e[i].to] && e[i].w)
{
level[e[i].to]=level[t]+;
Q.push(e[i].to);
}
}
}
return level[TTT];
} int Dfs(const int S,const int bk)
{
if(S==TTT)return bk;
int rest=bk;
for(int &i=cur[S];i;i=e[i].next)
{
if(level[e[i].to]==level[S]+ && e[i].w)
{
int flow=Dfs(e[i].to,min(e[i].w,rest));
e[i].w-=flow;
e[i^].w+=flow;
if((rest-=flow)<=)break;
}
}
if(bk==rest)level[S]=;
return bk-rest;
} void Dinic()
{
while(Bfs(SSS))
{
memcpy(cur,e.p,sizeof(cur));
Flow+=Dfs(SSS,INF);
}
return ;
} int main()
{
int i,j,t,y; scanf("%d",&n);
for(i=;i<=n;++i)
{
scanf("%d",&t);
for(j=;j<=t;++j)
{
scanf("%d",&y);
cnt++;
e.Link(i,n+(cnt<<)-,INF);
e.Link(n+(cnt<<),y,INF);
}
} SS=n+cnt+cnt+,SSS=SS+,TTT=SSS+; for(i=;i<=cnt;++i)
e.Link(n+i+i-,n+i+i,INF),In[n+i+i-]--,In[n+i+i]++; for(i=n+;i<=n+cnt+cnt;++i)
if(In[i]>)e.Link(SSS,i,In[i]);
else e.Link(i,TTT,-In[i]); for(i=;i<=n;++i)e.Link(SS,i,INF); i=;
while(Flow!=cnt)
{
e.Link(SSS,SS,);
Dinic();i++;
} printf("%d\n",i); return ;
}

最新文章

  1. 【系统篇】从int 3探索Windows应用程序调试原理
  2. 转: Protobuf 的 proto3 与 proto2 的区别
  3. 76 mkswaP-用于设置交换区
  4. 用python代码做configure文件
  5. day8-多进程和多线程
  6. [3D跑酷] GameManager
  7. [Effective JavaScript 笔记]第30条:理解prototype、getPrototypeOf和__ptoto__之间的不同
  8. (转)oracle字符集与汉字
  9. C#中使用GUID的笔记
  10. Img图片超过了DIV的最大宽度 解决方案
  11. java中int,char,string三种类型的相互转换
  12. 新的表格展示利器 Bootstrap Table
  13. COM学习(四)——COM中的数据类型
  14. Python入门之装饰器九步学习入门
  15. 10 Django RESTful api 实现匿名访问
  16. 使用ssh登录kali
  17. 【设计模式】jdbc桥连接过程解析
  18. 关于linux-Centos 7下mysql 5.7.9的rpm包的安装方式
  19. crontab详细用法
  20. NSScanner

热门文章

  1. poj1201 Intervals——差分约束
  2. PCB ODB++(Gerber)图形绘制实现方法
  3. python--修改默认递归层级
  4. 【BZOJ4025】二分图(可撤销并查集+线段树分治)
  5. 【NOIP练习赛】开车
  6. ACM_ZHANGZHANG喜欢手表
  7. hibernate annotation 之 一对多、多对一双向外键关联
  8. Java&amp;Xml教程(三)使用DOM方式修改XML文件内容
  9. x264
  10. JS——scroll封装