我爱网络流之最大流Dinic
2024-09-05 07:14:42
直接上大佬博客：
模板步骤：
第一步，先bfs把图划分成分成分层图网络
第二步，dfs多次找增广路
当前弧优化：即每一次dfs增广时不从第一条边开始，而是用一个数组cur记录点u之前循环到了哪一条边，以此来加速
裸的最大流，直接按题意建图跑就行
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=,inf=;
struct Side{
int v,ne,w;
}S[N<<];
int n,sn,head[N],cur[N],dep[N];
void init()
{
sn=;
for(int i=;i<=n;i++)
head[i]=-;
}
void add(int u,int v,int w)
{
S[sn].v=v;
S[sn].w=w;
S[sn].ne=head[u];
head[u]=sn++;
}
void addE(int u,int v,int w)
{
add(u,v,w);
add(v,u,);
}
bool bfs()
{
queue<int> q;
for(int i=;i<=n;i++)
dep[i]=;
dep[]=;
q.push();
int x,y;
while(!q.empty())
{
x=q.front();
q.pop();
for(int i=head[x];~i;i=S[i].ne)
{
y=S[i].v;
if(S[i].w>&&!dep[y])
{
dep[y]=dep[x]+;
q.push(y);
}
}
}
return dep[n]!=;
}
int dfs(int u,int minf)
{
if(u==n||!minf)
return minf;
int v,flow;
for(int &i=cur[u];~i;i=S[i].ne)
{
v=S[i].v;
if(dep[v]==dep[u]+&&S[i].w>)
{
flow=dfs(v,min(minf,S[i].w));
if(flow)
{
S[i].w-=flow;
S[i^].w+=flow;
return flow;
}
}
}
return ;
}
int dinic()
{
int ans=,flow;
while(bfs())
{
for(int i=;i<=n;i++)
cur[i]=head[i];
while(flow=dfs(,inf))
ans+=flow;
}
return ans;
}
int main()
{
int m,u,v,w;
while(~scanf("%d%d",&m,&n))
{
init();
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
addE(u,v,w);
}
printf("%d\n",dinic());
}
return ;
}
小桥流水人家
也是个裸的最大流，不过得看得出来，就把每周每天视为节点，然后弄个汇点跟源点，跑一遍dinic看最大流是不是总要求的天数
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=,inf=;
struct Side{
int v,ne,w;
}S[N<<];
struct Film{
int ok[],day,week;
}F[N];
int n,sn,sum,sb,se,head[N],cur[N],dep[N];
void init()
{
sn=,sum=;
sb=,se=n+;
for(int i=;i<=se;i++)
head[i]=-;
}
void add(int u,int v,int w)
{
S[sn].v=v;
S[sn].w=w;
S[sn].ne=head[u];
head[u]=sn++;
}
void addE(int u,int v,int w)
{
add(u,v,w);
add(v,u,);
}
bool bfs()
{
queue<int> q;
for(int i=;i<=se;i++)
dep[i]=;
dep[sb]=;
q.push(sb);
int u,v;
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u];~i;i=S[i].ne)
{
v=S[i].v;
if(S[i].w>&&!dep[v])
{
dep[v]=dep[u]+;
q.push(v);
}
}
}
return dep[se]!=;
}
int dfs(int u,int minf)
{
if(u==se||!minf)
return minf;
int v,flow;
for(int &i=cur[u];~i;i=S[i].ne)
{
v=S[i].v;
if(S[i].w>&&dep[v]==dep[u]+)
{
flow=dfs(v,min(minf,S[i].w));
if(flow>)
{
S[i].w-=flow;
S[i^].w+=flow;
return flow;
}
}
}
return ;
}
int dinic()
{
int ans=,flow;
while(bfs())
{
for(int i=;i<=se;i++)
cur[i]=head[i];
while(flow=dfs(sb,inf))
ans+=flow;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
scanf("%d",&F[i].ok[j]);
scanf("%d%d",&F[i].day,&F[i].week);
sum+=F[i].day;
}
for(int i=;i<=n;i++)
addE(sb,i,F[i].day);
for(int i=;i<=n;i++)
{
for(int j=;j<F[i].week;j++)
for(int k=;k<=;k++)
if(F[i].ok[k])
addE(i,n+j*+k,);
}
for(int i=;i<;i++)
for(int j=;j<=;j++)
addE(n+i*+j,se,);
if(dinic()>=sum)
printf("Yes\n");
else
printf("No\n");
}
return ;
}
one day day
100000个人，但才10个星球，在建图上，把可以去的星球状态相同的人视为一样的，这样最多就才1024个状态，然后跑一遍dinic，c++直接交，g++的话得用快读。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=<<,inf=;
struct Side{
int v,ne,w;
}S[N<<];
int sn,pb,pe,n,m,head[N],cur[N];
int cf2[]={},man[N],dep[N];
//int read()
//{
// int res = 0, flg = 1; char chr = getchar();
// while(chr < '0' || chr > '9') {if(chr == '-') res = -1; chr = getchar();}
// while(chr <= '9' && chr >= '0') {res = res * 10 + chr - '0'; chr = getchar();}
// return res * flg;
//}g++用快读
void init()
{
sn=;
pb=,pe=cf2[m]+m;
for(int i=;i<cf2[m];i++)
man[i]=;
for(int i=;i<=pe;i++)
head[i]=-;
}
void add(int u,int v,int w)
{
S[sn].w=w;
S[sn].v=v;
S[sn].ne=head[u];
head[u]=sn++;
}
void addE(int u,int v,int w)
{
add(u,v,w);
add(v,u,);
}
bool bfs()
{
for(int i=;i<=pe;i++)
dep[i]=;
dep[pb]=;
queue<int> q;
q.push(pb);
int u,v;
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u];~i;i=S[i].ne)
{
v=S[i].v;
if(S[i].w>&&!dep[v])
{
dep[v]=dep[u]+;
q.push(v);
}
}
}
return dep[pe]!=;
}
int dfs(int u,int minf)
{
if(u==pe||!minf)
return minf;
int v,flow;
for(int &i=cur[u];~i;i=S[i].ne)
{
v=S[i].v;
if(S[i].w>&&dep[v]==dep[u]+)
{
flow=dfs(v,min(minf,S[i].w));
if(flow)
{
S[i].w-=flow;
S[i^].w+=flow;
return flow;
}
}
}
return ;
}
int dinic()
{
int maxf=,flow;
while(bfs())
{
for(int i=;i<=pe;i++)
cur[i]=head[i];
while(flow=dfs(pb,inf))
maxf+=flow;
}
return maxf;
}
int main()
{
for(int i=;i<=;i++)
cf2[i]=cf2[i-]<<;
int num,x;
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=;i<=n;i++)
{
num=;
for(int j=;j<m;j++)
{
scanf("%d",&x);
if(x)
num|=cf2[j];
}
man[num]++;
}
for(int i=;i<cf2[m];i++)
if(man[i])
{
addE(pb,i,man[i]);
for(int j=;j<m;j++)
if(i&cf2[j])
addE(i,cf2[m]+j,man[i]);
}
for(int i=;i<m;i++)
{
scanf("%d",&x);
addE(cf2[m]+i,pe,x);
}
if(dinic()>=n)
printf("YES\n");
else
printf("NO\n");
}
return ;
}
流浪星球
啊，网络流就在于建图。
最新文章
- Django进阶2
- mvc4 ajax.beginform表单验证
- 黑客攻防技术宝典Web实战篇（二）工具篇
- TypeScript开发手册
- 位图索引:原理（BitMap index）
- 分享到QQ空间代码(一)
- 转载 WebBrowser介绍——Javascript与C++互操作
- mysql 1130 ERROR 1130: Host xxx.xxx.xxx.xxx is not allowed to connect to this MySQL server
- nginx 配置http2
- @DataProvider Method 参数传递
- AndroidStudio常见提示
- OpenGL ES 三种类型 uniform attribute varying
- 前端 TDD 开发
- Log4j各级别日志重复打印
- PHP 3 运算符 if...else...elseif 语句
- [转] 解决Driver/library version mismatch
- c groups
- laravel 数据验证
- 用POP动画模拟真实秒钟摆动效果
- HDU 6158 笛卡尔定理 几何