网络流24题笔记

其实网络流、费用流、上下界 都写了不少了

加起来 也能凑个50道

可是最近觉得BJ的网络流水平愈发下降 很多题看不出来

于是决定系统的刷一刷网络流24题

// 每个小标题都是题目传送门

1.搭配飞行员

裸的二分图最大匹配..

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=210;
int last[N],ecnt;
struct EDGE{int to,nt;}e[N*N];
inline void add(int u,int v)
{e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}
int vis[N],tim;
int match[N];
bool hungray(int u)
{
for(int i=last[u],v;i;i=e[i].nt)
{
v=e[i].to;
if(vis[v]==tim) continue;
vis[v]=tim;
if(!match[v] || hungray(match[v]))
{
match[v]=u;
match[u]=v;
return 1;
}
}
return 0;
}
int main()
{
freopen("flyer.in","r",stdin);
freopen("flyer.out","w",stdout);
int m=read(),n=read();
register int i,x,y;
while(scanf("%d%d",&x,&y)!=EOF)
{
if(x>m) swap(x,y);
add(x,y);add(y,x);
}
int ans(0);
for(i=1;i<=n;++i)
{
tim++;
if(hungray(i)) ans++;
}
if(!ans){puts("No Solution!");return 0;}
cout<<ans<<endl;
}

2.太空飞行计划

裸的最小割 用价值和减掉最少的代价

最后一遍bfs可以知道哪些点被割掉 //算是有收获吧

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=110,inf=0X3f3f3f3f;
int S=N-2,T=N-1;
int last[N],ecnt=1;
struct EDGE{int to,nt,val;}e[N*N<<2];
inline void readd(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
inline void add(int u,int v,int val)
{readd(u,v,val);readd(v,u,0);}
int d[N],q[N];
bool bfs()
{
memset(d,0,sizeof(d));
register int i,u,v,head(0),tail(1);
d[S]=1;q[head]=S;
while(head<tail)
{
u=q[head++];
for(i=last[u];i;i=e[i].nt)
if(e[i].val && !d[v=e[i].to])
q[tail++]=v,d[v]=d[u]+1;
}
return d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim) return lim;
int res=0;
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+1)
{
tmp=dfs(v,min(e[i].val,lim));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
int mxflow;
int dinic()
{while(bfs())mxflow+=dfs(S,inf);return mxflow;}
int pos[N];
int main()
{
int m=read(),n=read();
register int i,x;
register char opt;
int ans(0);
for(i=1;i<=m;++i)
{
x=read();
ans+=x;
add(i,T,x);
while(scanf("%d%c",&x,&opt))
{
add(x+m,i,inf);
if(opt=='n' || opt=='r') break;
}
}
for(i=1;i<=n;++i)
x=read(),add(S,i+m,x);
ans-=dinic();
for(i=1;i<=m;++i)
if(!d[i]) printf("%d ",i);cout<<endl;
for(i=m+1;i<=m+n;++i)
if(!d[i]) printf("%d ",i-m);cout<<endl;
cout<<ans<<endl;
return 0;
}

3.最小路径覆盖

如题...http://blog.csdn.net/blackjack_/article/details/72330666

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=510,inf=0X3f3f3f3f;
int last[N],ecnt;
struct EDGE{int to,nt;}e[N*N];
inline void add(int u,int v)
{e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}
int n,m;
int match[N];
int vis[N],tim;
int hungray(int u)
{
for(int i=last[u],v;i;i=e[i].nt)
{
v=e[i].to;
if(vis[v]==tim) continue;
vis[v]=tim;
if(!match[v] || hungray(match[v]))
{
match[v]=u;match[u]=v;
return 1;
}
}
return 0;
}
inline void out(int x)
{
while(match[x+n]) x=match[x+n];
while(x+n)
{
vis[x]=tim;
printf("%d ",x);
x=match[x]-n;
}
puts("");
}
int main()
{
n=read(),m=read();
register int i,u,v;
for(i=1;i<=m;++i)
u=read(),v=read(),
add(u,v+n),add(v+n,u);
int ans(0);
for(i=1;i<=n;++i)
tim++,ans+=hungray(i);
tim++;
for(i=1;i<=n;++i)
if(vis[i]!=tim)
out(i);
cout<<n-ans<<endl;
}

4.魔术球

这题挺好做的 // 直接贪心往里放就行...

之前没想到贪心就能过 老老实实写了匈牙利

首先 我们发现 由于加入有序 所以所有可能的添加方式会形成一个DAG

而且显然对于这样的一个DAG 只要n>=最小不相交路径覆盖 就能按照这个覆盖填数

所以二分一下答案之后匈牙利算法判定 //跑一跑发现 55 是 1567 所以空间不会爆 /捂脸熊

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=4010;
int last[N],ecnt;
struct EDGE{int to,nt;}e[N*N];
inline void add(int u,int v)
{e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}
int n,ans;
int match[N];
int vis[N],tim;
int hungray(int u)
{
for(int i=last[u],v;i;i=e[i].nt)
{
v=e[i].to;
if(vis[v]==tim) continue;
vis[v]=tim;
if(!match[v] || hungray(match[v]))
{
match[v]=u;match[u]=v;
return 1;
}
}
return 0;
}
inline bool magic(int i,int j)
{
int x(i+j);
x=floor(sqrt(x));
return x*x==i+j;
}
void initial()
{
ecnt=tim=0;
memset(vis,0,sizeof(vis));
memset(last,0,sizeof(last));
memset(match,0,sizeof(match));
}
bool check(int x)
{
initial();
register int i,j,res(0);
for(i=1;i<=x;++i)
for(j=i+1;j<=x;++j)
if(magic(i,j))
add(i,j+x),add(j+x,i);
for(i=1;i<=x;++i)
tim++,res+=hungray(i);
return x-res<=n;
}
inline void out(int x)
{
while(match[x+ans]) x=match[x+ans];
while(x+ans)
{
vis[x]=tim;
printf("%d ",x);
x=match[x]-ans;
}
puts("");
}
int main()
{
n=read();
register int i,l(1),r(1600),mid;
while(l<=r)
{
mid=(l+r)>>1;
check(mid) ? l=mid+1 : r=mid-1;
}
ans=l-1;
check(ans);
cout<<ans<<endl;
tim++;
for(i=1;i<=ans;++i)
if(vis[i]!=tim)
out(i);
return 0;
}

5.圆桌聚餐

这个题是来搞笑的么...

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=510,inf=0X3f3f3f3f;
int S(N-2),T(N-1);
int last[N],ecnt=1;
struct EDGE{int to,nt,val;}e[N*N];
inline void readd(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
inline void add(int u,int v,int val)
{readd(u,v,val);readd(v,u,0);}
int n,m;
int d[N],q[N];
bool bfs()
{
memset(d,0,sizeof(d));
register int i,u,v,head(0),tail(1);
d[S]=1;q[head]=S;
while(head<tail)
{
u=q[head++];
for(i=last[u];i;i=e[i].nt)
if(e[i].val && !d[v=e[i].to])
q[tail++]=v,d[v]=d[u]+1;
}
return d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim) return lim;
int res(0);
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+1)
{
tmp=dfs(v,min(e[i].val,lim));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
int mxflow;
void dinic()
{while(bfs())mxflow+=dfs(S,inf);}
int main()
{
m=read();n=read();
register int i,j,x,sum(0);
for(i=1;i<=m;++i)
x=read(),sum+=x,add(S,i,x);
for(i=1;i<=n;++i)
x=read(),add(i+m,T,x);
for(i=1;i<=m;++i)
for(x=1;x<=n;++x)
add(i,x+m,1);
dinic();
if(mxflow!=sum){puts("0");return 0;}
puts("1");
for(i=1;i<=m;++i)
{
for(j=last[i];e[j].to!=S;j=e[j].nt)
if(!e[j].val)
printf("%d ",e[j].to-m);
puts("");
}
}

6.最长递增子序列

没看懂题 之后查题解 看到一篇blog的名称 我就不用读题了。。。

最小不相交路径覆盖。。。//是我理解能力太差还是题面真的鬼畜。。。

气的宝宝不想写。。

7.试题库

这个和圆桌聚餐有区别吗-_- //感到深深的失望

8.方格取数

太过经典以至于BJ都会。。。

当直接像不好做的时候 我们就正难则反来最小割了

格子黑白染色之后 相邻的黑白格子至少有一边被割掉 所以连inf

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=1010,inf=0X3f3f3f3f;
int S(N-2),T(N-1);
int last[N],ecnt=1;
struct EDGE{int to,nt,val;}e[N*N];
inline void readd(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
inline void add(int u,int v,int val)
{readd(u,v,val);readd(v,u,0);}
int n,m;
int d[N],q[N];
bool bfs()
{
memset(d,0,sizeof(d));
register int i,u,v,head(0),tail(1);
d[S]=1;q[head]=S;
while(head<tail)
{
u=q[head++];
for(i=last[u];i;i=e[i].nt)
if(e[i].val && !d[v=e[i].to])
q[tail++]=v,d[v]=d[u]+1;
}
return d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim) return lim;
int res(0);
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+1)
{
tmp=dfs(v,min(e[i].val,lim));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
int mxflow;
void dinic()
{while(bfs())mxflow+=dfs(S,inf);}
int main()
{
m=read();n=read();
register int i,j,x,sum(0);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
{
x=read();sum+=x;
(i+j)&1 ? add(S,(i-1)*n+j,x) : add((i-1)*n+j,T,x);
}
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
if((i+j)&1)
{
int now=(i-1)*n+j;
if(i>1) add(now,now-n,inf);
if(j>1) add(now,now-1,inf);
if(i<m) add(now,now+n,inf);
if(j<n) add(now,now+1,inf);
}
dinic();
cout<<sum-mxflow<<endl;
}

9.餐巾计划

我记得这是一道很经典的题 // 我也知道我忘干净了

重新做这一遍 发现自己还没有菜到经典题都不会

一步步YY的建图 最后在loj wa了仨点 觉得想不出更好的了

最后查题解 按照他说的建图 结果T了仨点 之后开心发现空间开小了...

然后一想 我的建图和题解其实一模一样啊... 就是思路不同

讲一讲BJ的思路 //觉得那个二分图的想法太不靠谱

首先当然是建个分裂中期的图 // 高中生物渣渣BJ

如果天真的直接从i->i+M连个费用为F的边 就会发现很GG

那么我们的目标就是给拿去洗的餐巾费用为0的流量

那么就不妨新建n个点来表示用来洗的 i+n直接向i+M连边就行

这个时候怎么办呢 显然 这一天用完的可以全拿去洗 那么点i+n的流量就是ri

之后这一天洗的以后也能洗 所以i+n+k向i+n+k+1有流量inf费用0的边

之后就做完啦

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=2010,inf=0X3f3f3f3f;
int S=N-2,T=N-1;
int last[N],ecnt=1;
struct EDGE{int fr,to,nt,val,ct;}e[N*N];
inline void readd(int u,int v,int val,int ct)
{e[++ecnt]=(EDGE){u,v,last[u],val,ct};last[u]=ecnt;}
inline void add(int u,int v,int val,int ct)
{readd(u,v,val,ct);readd(v,u,0,-ct);}
int d[N],q[N],from[N];
bool inq[N];
bool spfa()
{
memset(d,0X3f,N<<2);
register int i,u,v,head(0),tail(1);
q[head]=S;d[S]=0;inq[S]=1;
while(head^tail)
{
u=q[head++];if(head==N) head=0;
inq[u]=0;
for(i=last[u];i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]>d[u]+e[i].ct)
{
d[v]=d[u]+e[i].ct;
from[v]=i;
if(!inq[v])
{
inq[v]=1,q[tail++]=v;
if(tail==N) tail=0;
}
}
}
return d[T]!=inf;
}
int ans;
void mincf()
{
register int i,tmp;
while(spfa())
{
tmp=inf;
for(i=from[T];i;i=from[e[i].fr])
tmp=min(tmp,e[i].val);
for(i=from[T];i;i=from[e[i].fr])
e[i].val-=tmp,e[i^1].val+=tmp,ans+=e[i].ct*tmp;
}
}
int main()
{
int n=read(),P=read(),M=read(),F=read(),N=read(),s=read();
register int i,x;
for(i=1;i<=n;++i)
x=read(),
add(S,i,inf,P),add(S,i+n,x,0),add(i,T,x,0);
for(i=1;i<n;++i)
add(i,i+1,inf,0);
for(i=1;i<=n-M;++i)
add(i+n,i+M,inf,F);
for(i=1;i<=n-N;++i)
add(i+n,i+N,inf,s);
mincf();
cout<<ans<<endl;
return 0;
}

10.软件补丁

这个题是 真·来搞笑啊 ...

解题思路如下：

网络流网络流网络流...网络流网络流网络流...网络流......去你大爷的网络流

建图spfa建图spfa 空间不够空间不够

dpdpdp 没后效性没后效性 spfaspfaspfa

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=(1<<20)+100,inf=0X3f3f3f3f;
int b[110][2],f[110][2],c[110];
int d[N],q[N];
bool inq[N];
char s[30];
int main()
{
int n=read(),m=read();
memset(d,0X3f,sizeof(d));
register int i,j,u,v,head(0),tail(1);
for(i=1;i<=m;++i)
{
c[i]=read();
scanf("%s",s+1);
for(j=1;j<=n;++j)
if(s[j]=='+') b[i][0]|=1<<j-1;
else if(s[j]=='-') b[i][1]|=1<<j-1;
scanf("%s",s+1);
for(j=1;j<=n;++j)
if(s[j]=='-') f[i][0]|=1<<j-1;
else if(s[j]=='+') f[i][1]|=1<<j-1;
}
q[head]=(1<<n)-1;
d[(1<<n)-1]=0;inq[(1<<n)-1]=1;
while(head<tail)
{
u=q[head++];inq[u]=0;
if(head==N) head=0;
for(i=1;i<=m;++i)
if((u&b[i][0])==b[i][0] && !(u&b[i][1]))
if(d[v=(u^(u&f[i][0]))|f[i][1]]>d[u]+c[i])
{
d[v]=d[u]+c[i];
if(!inq[v])
{
inq[v]=1,q[tail++]=v;
if(tail==N) tail=0;
}
}
}
if(d[0]==inf) puts("0");
else cout<<d[0]<<endl;
return 0;
}

11.数字梯形

被 loj 题面坑了啊...

我就说我咋都想不明白样例咋跑的...给个图啊喂

这个题叫的高级点就叫：最大权不相交路径

不就是裸的最大费用最大流...

第一问限制流量 就一个点拆成俩...

第二三问逐渐放开 就改改流量上限就行了...

很好奇那些重新建图的是不是嫌code少...

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=2010,inf=0X3f3f3f3f;
int S=N-2,T=N-1;
int last[N],ecnt=1;
struct EDGE{int to,nt,val,ct;}e[N<<3];
inline void readd(int u,int v,int val,int ct)
{e[++ecnt]=(EDGE){v,last[u],val,ct};last[u]=ecnt;}
inline void add(int u,int v,int val,int ct)
{readd(u,v,val,ct);readd(v,u,0,-ct);}
int ans;
int d[N],q[N],vis[N],tim;
bool inq[N];
bool spfa()
{
tim++;
memset(d,-1,sizeof(d));
register int i,u,v,head(0),tail(1);
q[head]=S;d[S]=0;inq[S]=1;
while(head!=tail)
{
u=q[head++];inq[u]=0;
if(head==N) head=0;
for(i=last[u];i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]<d[u]+e[i].ct)
{
d[v]=d[u]+e[i].ct;
if(!inq[v])
{
inq[v]=1,q[tail++]=v;
if(tail==N) tail=0;
}
}
}
return ~d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim)
{ans+=d[u]*lim;return lim;}
int res(0);
vis[u]=tim;
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+e[i].ct && vis[v]!=tim)
{
tmp=dfs(v,min(lim,e[i].val));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
void maxcf()
{while(spfa())dfs(S,inf);}
int mp[50][50],ct[N];
int main()
{
int m=read(),n=read();
register int i,j,tot(0);
for(i=1;i<=n;++i)
for(j=1;j<=m+i-1;++j)
mp[i][j]=++tot,
ct[tot]=read();
for(i=1;i<=tot;++i)
add(i,i+tot,1,ct[i]);
for(i=1;i<n;++i)
for(j=1;j<=m+i-1;++j)
{
add(mp[i][j]+tot,mp[i+1][j],1,0);
add(mp[i][j]+tot,mp[i+1][j+1],1,0);
}
for(i=1;i<=n+m-1;++i)
add(mp[n][i]+tot,T,inf,0);
for(i=1;i<=m;++i)
add(S,i,1,0);
maxcf();
cout<<ans<<endl;
for(i=2;i<=ecnt;i+=2)
e[i].val+=e[i^1].val,
e[i^1].val=0;
for(i=2;i<=tot<<1;i+=2)
e[i].val=inf;
ans=0;
maxcf();
cout<<ans<<endl;
for(i=2;i<=ecnt;i+=2)
e[i].val+=e[i^1].val,
e[i^1].val=0;
for(i=tot+1<<1;i<=ecnt-(m<<1);i+=2)
e[i].val=inf;
ans=0;
maxcf();
cout<<ans<<endl;
return 0;
}

12.运输问题

er... 你敢不敢再裸点

13.分配问题

同上

24题咋还质量递减呐？ 浪费宝宝的青春啊

14.负载平衡

怎么来形容看到这道题的感受呢...震惊...

记得这是一道神题啊...

这个题还有网络流做法啊...靠...随便做啊...

// 环里的点连流量inf 费用1 环内环外的域作为源汇 分别连流量为仓库容量和ave

让我们来回顾hzwer的题解 //这是个传送门

15.最长 k 可重区间集

以前做的时候好好想过 但是忘了

说明当时并没有看透本质 唉

感觉这个思想 emm 不太好说...

就是考虑最多只能有k个重合

那么不妨把重合的部分拆开

这样就变成了最多k条不相交路径

所以我们给流量为k 两个不会重合的之间可以连通

这样就跑出了k个不相交路径了

下面这个链接就很详尽了

http://blog.csdn.net/blackjack_/article/details/72457147

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=1100,inf=0X3f3f3f3f;
struct node{int l,r;}p[N];
int V[N],tot;
inline int get_hash(int x)
{
register int l(1),r(tot),mid;
while(l<=r)
{
mid=(l+r)>>1;
V[mid]<=x ? l=mid+1 : r=mid-1;
}
return l-1;
}
int S(N-2),T(N-1),ans;
int last[N],ecnt=1;
struct EDGE{int to,nt,val,ct;}e[N<<3];
inline void readd(int u,int v,int val,int ct)
{e[++ecnt]=(EDGE){v,last[u],val,ct};last[u]=ecnt;}
inline void add(int u,int v,int val,int ct)
{readd(u,v,val,ct);readd(v,u,0,-ct);}
int d[N],q[N],vis[N],tim;
bool inq[N];
bool spfa()
{
tim++;
memset(d,-1,sizeof(d));
register int i,u,v,head(0),tail(1);
q[head]=S;inq[S]=1;d[S]=0;
while(head!=tail)
{
u=q[head++];inq[u]=0;
if(head==N) head=0;
for(i=last[u];i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]<d[u]+e[i].ct)
{
d[v]=d[u]+e[i].ct;
if(!inq[v])
{
inq[v]=1;q[tail++]=v;
if(tail==N) tail=0;
}
}
}
return ~d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim){ans+=d[u]*lim;return lim;}
vis[u]=tim;
int res(0);
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+e[i].ct && vis[v]!=tim)
{
tmp=dfs(v,min(e[i].val,lim));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
void maxcf()
{while(spfa()) dfs(S,inf);}
int main()
{
int n=read(),K=read();
register int i;
for(i=1;i<=n;++i)
{
p[i].l=read();p[i].r=read();
if(p[i].l>p[i].r) swap(p[i].l,p[i].r);
V[i]=p[i].l;V[i+n]=p[i].r;
}
sort(V+1,V+1+(n<<1));
V[++tot]=V[1];
for(i=2;i<=n<<1;++i)
if(V[i]!=V[i-1])
V[++tot]=V[i];
add(S,1,K,0);add(tot,T,K,0);
for(i=1;i<tot;++i) add(i,i+1,inf,0);
for(i=1;i<=n;++i)
add(get_hash(p[i].l),get_hash(p[i].r),1,p[i].r-p[i].l);
maxcf();
cout<<ans<<endl;
}

16.星际转移

这个题太虎了...

枚举时间 每个时间都新开一排点 跑残量网络就行

BJ觉得是能卡掉 所以就一直想怎么优化 结果没想到 最后看题解 觉得真low...

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=55,M=5010,inf=0X3f3f3f3f;
int S(M-2),T(M-1);
int last[M],ecnt(1);
struct EDGE{int to,nt,val;}e[M*1000];
inline void readd(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
inline void add(int u,int v,int val)
{readd(u,v,val);readd(v,u,0);}
int d[M],q[M];
bool bfs()
{
memset(d,0,sizeof(d));
register int i,u,v,head(0),tail(1);
q[head]=S;d[S]=1;
while(head<tail)
{
u=q[head++];
for(i=last[u];i;i=e[i].nt)
if(e[i].val && !d[v=e[i].to])
d[v]=d[u]+1,q[tail++]=v;
}
return d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim) return lim;
int res(0);
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]==d[u]+1)
{
tmp=dfs(v,min(lim,e[i].val));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
int mxflow;
void dinic()
{while(bfs())mxflow+=dfs(S,inf);}
int H[N],s[N][N];
int Fa[N];
inline int find(int x)
{return Fa[x]==x ? x : Fa[x]=find(Fa[x]);}
int main()
{
int n=read(),m=read(),K=read();
register int i,j,t;
for(i=1;i<=n+2;++i) Fa[i]=i;
for(i=1;i<=m;++i)
{
H[i]=read();
s[i][0]=read();
for(j=1;j<=s[i][0];++j) s[i][j]=read()+2;
s[i][s[i][0]+1]=s[i][1];
if(H[i])for(j=2;j<=s[i][0];++j) Fa[find(s[i][j])]=find(s[i][j-1]);
// 1<-the moon 2<-the earth
}
if(K==0 || find(1)!=find(2))
{puts("0");return 0;}
add(S,2,K);
add(1,T,inf);
int ans(0);
while(1)
{
ans++;
for(i=1;i<=m;++i)
{
t=(ans-1)%s[i][0];
add((ans-1)*(n+2)+s[i][t+1],ans*(n+2)+s[i][t+2],H[i]);
}
for(i=1;i<=n+2;++i)
add((ans-1)*(n+2)+i,ans*(n+2)+i,inf);
add(ans*(n+2)+1,T,inf);
dinic();
if(mxflow==K)
{cout<<ans<<endl;return 0;}
}
return 0;
}

17.孤岛营救问题

又又又有奇怪的题目混进来了QwQ

状压spfa... md亏我绞尽脑汁想建图...

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=15,inf=0X3f3f3f3f,M=N*N*((1<<10)+100);
const int trans[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,P,K;
int mp[N][N][N][N];
vector<int> vec[N][N];
int f[N][N][(1<<10)+100];
int q[M][3];
bool inq[N][N][(1<<10)+100];
void spfa()
{
memset(f,0X3f,sizeof(f));
register int i,j,head(0),tail(1),x,y,s(0),aimx,aimy,aims;
for(j=0;j<vec[1][1].size();++j)
s|=1<<vec[1][1][j];
f[1][1][s]=0;inq[1][1][s]=1;
q[head][0]=q[head][1]=1;q[head][2]=s;
while(head!=tail)
{
x=q[head][0];y=q[head][1];s=q[head++][2];
if(head==M) head=0;
inq[x][y][s]=0;
for(i=0;i<4;++i)
{
aimx=x+trans[i][0];
aimy=y+trans[i][1];
if(~mp[x][y][aimx][aimy] && (((s>>mp[x][y][aimx][aimy])&1) || mp[x][y][aimx][aimy]==inf))
{
aims=s;
for(j=0;j<vec[aimx][aimy].size();++j)
aims|=1<<vec[aimx][aimy][j];
if(f[aimx][aimy][aims]>f[x][y][s]+1)
{
f[aimx][aimy][aims]=f[x][y][s]+1;
if(!inq[aimx][aimy][aims])
{
inq[aimx][aimy][aims]=1;
q[tail][0]=aimx;
q[tail][1]=aimy;
q[tail++][2]=aims;
if(tail==M) tail=0;
}
}
}
}
}
}
int main()
{
n=read();m=read();P=read();K=read();
register int i,x1,x2,y1,y2;
memset(mp,-1,sizeof(mp));
for(x1=1;x1<=n;++x1)
for(y1=1;y1<=m;++y1)
for(i=0;i<4;++i)
{
x2=x1+trans[i][0];
y2=y1+trans[i][1];
if(x2<1 || y2<1 || x2>n || y2>m) continue;
mp[x1][y1][x2][y2]=inf;
}
for(i=1;i<=K;++i)
{
x1=read(),y1=read(),x2=read(),y2=read();
mp[x1][y1][x2][y2]=mp[x2][y2][x1][y1]=read()-1;
}
int S=read();
for(i=1;i<=S;++i)
{
x1=read(),y1=read();x2=read()-1;
vec[x1][y1].push_back(x2);
}
spfa();
int ans(inf);
for(i=0;i<(1<<P);++i)
ans=min(ans,f[n][m][i]);
if(ans==inf) puts("-1");
else cout<<ans<<endl;
return 0;
}

18.航空路线问题

题目显然是求最大权不相交路径

拆点限制下流量 再特判下1,n之间连边就行了

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=310,inf=0X3f3f3f3f;
int S=N-2,T=N-1;
int last[N],ecnt=1;
struct EDGE{int to,nt,val,ct;}e[N*N<<1];
inline void readd(int u,int v,int val,int ct)
{e[++ecnt]=(EDGE){v,last[u],val,ct};last[u]=ecnt;}
inline void add(int u,int v,int val,int ct)
{readd(u,v,val,ct);readd(v,u,0,-ct);}
int n,m,ans;
int d[N],q[N],vis[N],tim;
bool inq[N];
bool spfa()
{
tim++;
memset(d,-1,sizeof(d));
register int i,u,v,head(0),tail(1);
d[S]=0;q[head]=S;inq[S]=1;
while(head!=tail)
{
u=q[head++];inq[u]=0;
if(head==N) head=0;
for(i=last[u];i;i=e[i].nt)
if(e[i].val && d[v=e[i].to]<d[u]+e[i].ct)
{
d[v]=d[u]+e[i].ct;
if(!inq[v])
{
inq[v]=1;q[tail++]=v;
if(tail==N) tail=0;
}
}
}
return ~d[T];
}
int dfs(int u,int lim)
{
if(u==T || !lim){ans+=lim*d[u];return lim;}
vis[u]=tim;
int res(0);
for(int i=last[u],v,tmp;i;i=e[i].nt)
if(e[i].val && vis[v=e[i].to]!=tim && d[v]==d[u]+e[i].ct)
{
tmp=dfs(v,min(e[i].val,lim));
lim-=tmp;res+=tmp;
e[i].val-=tmp;e[i^1].val+=tmp;
if(!tmp) d[v]=-1;
if(!lim) break;
}
return res;
}
int mxflow;
void maxcf()
{while(spfa()) mxflow+=dfs(S,inf);}
string str[N];
map<string,int> mp;
int st[N],top;
void solve()
{
tim++;
maxcf();
if(mxflow!=2)
{puts("No Solution!");return ;}
cout<<ans<<endl;
register int i,u(n+1),v,pre;
while(1)
{
pre=u;
for(i=last[u];i;i=e[i].nt)
if(e[i].ct==1 && !e[i].val && vis[v=e[i].to]!=tim)
{
vis[v]=tim;u=v+n;
st[++top]=v;
break;
}
if(u==pre) break;
}
cout<<str[1]<<endl;
for(i=1;i<=top;++i) cout<<str[st[i]]<<endl;
u=n+1;top=0;
while(1)
{
pre=u;
for(i=last[u];i;i=e[i].nt)
if(e[i].ct==1 && !e[i].val && vis[v=e[i].to]!=tim)
{
vis[v]=tim;u=v+n;
st[++top]=v;
break;
}
if(u==pre) break;
}
while(top) cout<<str[st[top]]<<endl,top--;
cout<<str[1]<<endl;
}
char s[N];
int main()
{
n=read(),m=read();
register int i,u,v;
string x,y;
for(i=1;i<=n;++i)
cin>>str[i],mp[str[i]]=i;
for(i=1;i<=m;++i)
{
cin>>x>>y;
u=mp[x],v=mp[y];
if(u>v) swap(u,v);
add(u+n,v,1,1);
if(u==1 && v==n) add(u+n,v,1,1);
}
add(S,1,2,0);add(n<<1,T,2,0);
add(1,1+n,1,0);add(n,n<<1,1,0);
for(i=1;i<=n;++i) add(i,i+n,1,0);
solve();
}

19.汽车加油行驶问题

又又又有奇怪的题混进来啦

又是一道spfa...

话说边界写错了判的<0结果两天也没搞出来 直接拖后了24题进度

#include<cmath>
#include<ctime>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=110,M=N*N*20,inf=0X3f3f3f3f;
const int trans[2][4]={{0,0,-1,1},{-1,1,0,0}};
int n,K,A,B,C;
int mp[N][N],cost[N][N][11][4];
int q[M][3],dis[N][N][11];
bool inq[N][N][11];
void spfa()
{
memset(dis,0X3f,sizeof(dis));
register int head(0),tail(1),k,u[3],v[3];
q[head][0]=q[head][1]=1;q[head][2]=K;
dis[1][1][K]=0;
while(head!=tail)
{
u[0]=q[head][0],u[1]=q[head][1],u[2]=q[head++][2];
inq[u[0]][u[1]][u[2]]=0;
if(head==M) head=0;
u[2]&&!mp[u[0]][u[1]] ? v[2]=u[2]-1 : v[2]=K-1;
for(k=0;k<4;++k)
{
v[0]=u[0]+trans[0][k];
v[1]=u[1]+trans[1][k];
if(v[0]<1 || v[1]<1 || v[0]>n || v[1]>n || dis[v[0]][v[1]][v[2]]<=dis[u[0]][u[1]][u[2]]+cost[u[0]][u[1]][u[2]][k])
continue;
dis[v[0]][v[1]][v[2]]=dis[u[0]][u[1]][u[2]]+cost[u[0]][u[1]][u[2]][k];
if(!inq[v[0]][v[1]][v[2]])
{
q[tail][0]=v[0],q[tail][1]=v[1],q[tail++][2]=v[2];
inq[v[0]][v[1]][v[2]]=1;
if(tail==M) tail=0;
}
}
}
}
int main()
{
n=read();K=read();A=read(),B=read(),C=read();
register int i,j,k;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
mp[i][j]=read();
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=0;k<=K;++k)
if(!mp[i][j])
if(!k)
cost[i][j][k][1]=cost[i][j][k][3]=A+C,
cost[i][j][k][0]=cost[i][j][k][2]=A+B+C;
else
cost[i][j][k][0]=cost[i][j][k][2]=B;
else
cost[i][j][k][1]=cost[i][j][k][3]=A,
cost[i][j][k][0]=cost[i][j][k][2]=A+B;
spfa();
int ans(inf);
for(i=0;i<=K;++i)
ans=min(ans,dis[n][n][i]);
cout<<ans<<endl;
return 0;
}

20.深海机器人问题

裸的令人发指

21.火星探险问题

和上一题一样的裸题...残量网络里跑个路径就行了

22.骑士共存问题

诶呀 终于遇到BJ会做的经典题了

http://blog.csdn.net/blackjack_/article/details/72730728

23.最长k可重线段集问题

和区间没本质区别 听说开区间建图要搞一搞

没啥提升 就不写了

LOJ上的 就做完了

完结

最后

以上就是丰富嚓茶为你收集整理的网络流24题笔记网络流24题笔记的全部内容，希望文章能够帮你解决网络流24题笔记网络流24题笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。