网络流做题笔记
P4015 运输问题
题目
考虑这是费用流板子题。。。
直接钦定源点和汇点，跑 dinic
- 最大费用就将花费取反
P2766 最长不下降子序列问题
题目
给定正整数序列 \(x_1 \ldots, x_n\)。
- 计算其最长不下降子序列的长度 \(s\)。
- 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 \(s\) 的不下降子序列。
- 如果允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 \(s\) 的不下降子序列。
思路
题目
不是很会，看一眼题解还像就会了。。。
第一问
直接 \(f[i]=\max_{x[j]<=x[i]}(f[j]+1)\)
第二问
- 连接 \((i,n+i)\)，防止使用多次。
- 建立源点和汇点，如果 \(f[i]==1\)，连接 \((0,i)\)；如果 \(f[i]==n\)，连接 \((n+i,2n+1)\)
- 直接跑最大流
注意：以上建的边容量为 \(1\)
第三问
可以把 \((1,n+1),(n,2n),(0,1),(2n,2n+1)\) 的容量改为无穷大（存在这条边）
之后就跑最大流。。。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=555,inf=1e9;
int n,x[N],f[N],s,t;
struct edge
{
int v,w,nxt;
}e[N*N*N];
int head[N<<2],et=-1;
inline void add(int u,int v,int w)
{
e[++et].v=v;
e[et].w=w,e[et].nxt=head[u];
head[u]=et;
}
queue<int>q;
int dep[N<<2];
namespace dinic
{
inline int bfs()
{
while(!q.empty())q.pop();
q.push(s);
memset(dep,0,sizeof dep);
dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].nxt)
{
int v=e[i].v,w=e[i].w;
if(dep[v]||!w)continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return (dep[t]?1:0);
}
inline int dfs(int u,int flow)
{
if(u==t)return flow;
for(int i=head[u];i!=-1;i=e[i].nxt)
{
int v=e[i].v,w=e[i].w;
if(dep[v]!=dep[u]+1||!w)continue;
int ff=dfs(v,min(w,flow));
if(ff==0)dep[v]=inf;
if(ff>0)
{
e[i].w-=ff;
e[i^1].w+=ff;
return ff;
}
}
return 0;
}
int ans=0;
inline void mx()
{
int f;
while(bfs())
{
while(f=dfs(s,inf))
{
ans+=f;
}
}
cout<<min(n,ans)<<'\n';
}
}
int main()
{
cin>>n;
memset(head,-1,sizeof head);
et=-1;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}
int S=0;
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(x[j]<=x[i])f[i]=max(f[i],f[j]+1);
}
S=max(S,f[i]);
}
cout<<S<<'\n';
for(int i=1;i<=n;i++)
{
add(i,n+i,1);
add(n+i,i,0);
}
for(int i=1;i<=n;i++)
{
if(f[i]==1)
{
add(0,i,1);
add(i,0,0);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(x[j]<=x[i]&&f[i]==f[j]+1)
{
add(j+n,i,1);
add(i,j+n,0);
}
}
}
for(int i=1;i<=n;i++)
{
if(f[i]==S)
{
add(i+n,2*n+1,1);
add(2*n+1,i+n,0);
}
}
s=0,t=2*n+1;
dinic::mx();
add(1,n+1,inf);add(n+1,1,0);add(n,2*n,inf);add(2*n,n,0);
add(0,1,inf);add(1,0,0);
if(f[n]==S)
{
add(2*n,2*n+1,inf);
add(2*n+1,2*n,0);
}
s=0,t=2*n+1;
dinic::mx();
return 0;
}
Steady Cow Assignment
传送门：1 2
思路
二分答案+网络流
具体地：
- 二分答案
- 枚举最低的等次 \(i\)，就可以知道只每只牛只能连向 \([i,i+mid-1]\)
- 建图：源点连向 \([1,n]\) 所有点，把 \([1,m]\) 连向 汇点
- 跑网络流，如果流量为 \(n\)，那就成功。
#include <bits/stdc++.h>
using namespace std;
const int N=1005,B=25,inf=1e9;
int n,m;
int c[N][N];
struct edge
{
int v,w,nxt;
}e[N*N*50];
int head[N<<5],et=-1;
inline void add(int u,int v,int w)
{
e[++et].v=v;
e[et].w=w,e[et].nxt=head[u];
head[u]=et;
}
int s=0,t=0;
int dep[N<<5],r[N];
queue<int>q;
namespace dinic
{
inline int bfs()
{
while(!q.empty())q.pop();
memset(dep,0,sizeof dep);
dep[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].nxt)
{
int v=e[i].v,w=e[i].w;
if(dep[v]||!w)continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return (dep[t]?1:0);
}
inline int dfs(int u,int flow)
{
if(u==t)return flow;
for(int i=head[u];i!=-1;i=e[i].nxt)
{
int v=e[i].v,w=e[i].w;
if(dep[v]!=dep[u]+1||!w)continue;
int ff=dfs(v,min(flow,w));
// if(ff==0)dep[v]=inf;
if(ff>0)
{
e[i].w-=ff;
e[i^1].w+=ff;
return ff;
}
}
return 0;
}
inline int mx()
{
int ans=0,f;
while(bfs())
{
while(f=dfs(s,inf))
{
ans+=f;
}
}
return ans;
}
}
inline int check(int mid)
{
for(int st=1;st<=m-mid+1;st++)
{
memset(head,-1,sizeof head);
et=-1;
for(int i=1;i<=n;i++)
{
add(0,i,1);
add(i,0,0);
}
for(int i=1;i<=n;i++)
{
for(int j=st;j<=st+mid-1;j++)
{
add(i,n+c[i][j],1);
add(n+c[i][j],i,0);
}
}
for(int j=1,mx;j<=m;j++)
{
add(n+j,n+m+1,r[j]);
add(n+m+1,n+j,0);
}
s=0,t=n+m+1;
int ans=dinic::mx();
if(ans==n)
{
return 1;
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
}
}
for(int i=1;i<=m;i++)cin>>r[i];
int l=0,r=m;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}