1「网络流 24 题」搭配飞行员
不说了,妥妥的最大流...
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=110; int link[N],tot,n,m,vis[N],match[N]; struct edge{int y,next;}a[N*N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y; a[tot].next=link[x]; link[x]=tot; } inline bool dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!vis[y]) { vis[y]=1; if(!match[y]||dfs(match[y])) {match[y]=x;return true;} } } return false; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); int x,y; while(cin>>x>>y) { add(x,y); } int ans=0; for(int i=1;i<=m;++i) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d",ans); return 0; }
2「网络流 24 题」太空飞行计划
好题,想了很长时间,都没得答案,最后才知道自己根本没学过这知识....
首先我们先简化题意：每个实验依赖某些仪器,每个实验有正的权值,每个仪器有负的权值,要求选出最大权值的方案.可以算是带权闭合图的模板了.我们将实验向他依赖的仪器连边,那么每个合法的方案就是一个闭合图(选出若干个点构成一个点集，使得每个点出边指向的点都在点集中).所以什么依赖什么就可以用闭合图写.
之后题目要求我们选出最大权值闭合图.我们构造出一个网络.将s连向所有正的点,容量为权值,所有负的点连向t,容量为权值的绝对值.之后根据依赖关系连边,容量为INF.结论：最小割后,s所在的集合即为最大带权闭合图.
证明：点这里
怎么说呢,这里说的简单一点,由于中间的容量都为INF,所以不可能被割断.所以最小割一定是简单割(割集的每一条边都与s或t有关.)而简单割一定对应一个闭合图(显然...)之后我们设x1为s集合中的正的点权值和,x2为负的点权值和.y1为t集合中的正的点权值和,y2为负的点权值和.
之后我们定义一个简单割的容量为C,则C=x2+y1.之后我们考虑N集合中的闭合图权值和为W=x1-x2，于是C+W=x2+y1+x1-x2=x1+y1=所有正的点权值和(我们设为tot).于是C+W=tot.W=tot-C，要是得W尽量大,我们可以将C尽量小.所以跑最小割没毛病...证毕.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=110,INF=1e9; int n,m,s,t,link[N],tot=1,d[N],current[N]; struct edge{int y,v,next;}a[N*N*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool bfs() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); memcpy(current,link,sizeof(current)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=d[x]+1; q.push(y); if(y==t) return true; } } return false; } inline int dinic(int x,int flow) { if(x==t) return flow; int rest=flow,k; for(int i=current[x];i&&rest;i=a[i].next) { current[x]=i; int y=a[i].y; if(d[y]==d[x]+1&&a[i].v) { k=dinic(y,min(rest,a[i].v)); if(!k) d[y]=-1; a[i].v-=k; a[i^1].v+=k; rest-=k; } } return flow-rest; } inline void work() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=1;q.push(y); } } } int main() { freopen("1.in","r",stdin); m=read();n=read(); s=0;t=n+m+1; int ans=0; for(int i=1;i<=m;++i) { int x;scanf("%d",&x); ans+=x; add(s,i,x); while(getchar()==' ') scanf("%d",&x),add(i,x+m,INF); } for(int i=1;i<=n;++i) { int x=read(); add(i+m,t,x); } int maxflow=0,flow; while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; work(); for(int i=1;i<=m;++i) if(d[i]) printf("%d ",i);puts(""); for(int i=1;i<=n;++i) if(d[i+m]) printf("%d ",i);puts(""); printf("%d",ans-maxflow); return 0; }
3「网络流 24 题」最小路径覆盖
这个算法进阶上有详细讲解,就不多说了,简单而言就是将每个店拆成出点与入点,构成二分图,最后跑最大匹配即可...
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=410,M=6010; int link[N],tot,matchx[N],matchy[N],n,m,vis[N],ans; struct edge{int y,next;}a[M]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y; a[tot].next=link[x]; link[x]=tot; } inline bool dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!vis[y]) { vis[y]=1; if(!matchy[y]||dfs(matchy[y])) {matchx[x]=y;matchy[y]=x;return true;} } } return false; } inline void dfs1(int x) { if(matchx[x]) { cout<<matchx[x]-n<<' '; vis[matchx[x]-n]=1; dfs1(matchx[x]-n); } } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;++i) { int x=read(),y=read(); add(x,y+n); } for(int i=1;i<=n;++i) { memset(vis,0,sizeof(vis)); if(dfs(i)) ++ans; } memset(vis,0,sizeof(vis)); // dfs1(1); for(int i=1;i<=n;++i) { if(matchx[i]&&!vis[i]) { cout<<i<<' '; vis[i]=1; dfs1(i); puts(""); } } printf("%d ",n-ans); return 0; }
4「网络流 24 题」魔术球
这种题就是如果不看题解,死活想不出来的题.....
我们分析题目发现这个题好像和杆子没有关系,因为全部都是球的操作,而且每一个杆子都是一串球的编号,这就启示我们将球与球之间连边.
每一条路径就是一个杆子,想到这里了我们就可以借用二分的思路,以此增加球的个数,判断杆子的数量是否符合答案.至于杆子的数量,考虑这是一个DAG,而且一个杆子就是一个路径,要求将所有的点都覆盖,那不就是最小路径覆盖吗？好了,就这吧....
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=10010; int link[N],tot,n,id,matchx[N],matchy[N],vis[N],now; struct edge{int y,next;}a[N*100]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y; a[tot].next=link[x]; link[x]=tot; } inline bool dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(vis[y]!=id) { vis[y]=id; if(!matchy[y]||dfs(matchy[y])) {matchx[x]=y;matchy[y]=x;return true;} } } return false; } inline void dfs1(int x) { int y=matchx[x]; if(y) { cout<<y<<' '; vis[y]=1; dfs1(y); } } int main() { freopen("1.in","r",stdin); n=read();now=0; int data; for(data=1;;data++) { for(int i=1;i<data;++i) if((int)sqrt(i+data)*(int)sqrt(i+data)==i+data) add(i,data); for(int i=1;i<=data;++i) { if(matchx[i]) continue; ++id; if(dfs(i)) ++now; } if(data-now>n) break; } //for(int i=1;i<11;++i) cout<<matchx[i]<<endl; printf("%d ",data-1); memset(vis,0,sizeof(vis)); for(int i=1;i<data;++i) { if(matchx[i]&&!vis[i]) { vis[i]=1; cout<<i<<' '; dfs1(i); puts(""); } } for(int i=1;i<data;++i) if(!vis[i]) cout<<i<<endl; return 0; }
5「网络流 24 题」圆桌聚餐
很典型的多重匹配问题,每一个地区的每一个人必须与一个餐桌进行匹配,由于一个地区的代表不能在一个餐桌上,所以一个地区向每一个餐桌连边的容量为1.最后检查最大流是否与总人数相等即可.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=430,INF=1e9; int m,n,link[N],tot=1,s,t,d[N],current[N]; struct edge{int y,next,v;}a[N*N*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool bfs() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); memcpy(current,link,sizeof(current)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=d[x]+1; q.push(y); if(y==t) return true; } } return false; } inline int dinic(int x,int flow) { if(x==t) return flow; int rest=flow,k; for(int i=current[x];i&&rest;i=a[i].next) { current[x]=i; int y=a[i].y; if(d[y]==d[x]+1&&a[i].v) { k=dinic(y,min(rest,a[i].v)); if(!k) d[y]=-1; a[i].v-=k; a[i^1].v+=k; rest-=k; } } return flow-rest; } int main() { freopen("1.in","r",stdin); m=read();n=read(); s=0;t=n+m+1; int ans=0; for(int i=1;i<=m;++i) { int x=read(); add(s,i,x); ans+=x; } for(int i=1;i<=n;++i) { int x=read(); add(i+m,t,x); } for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) add(i,j+m,1); int maxflow=0,flow; while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; if(maxflow<ans){printf("0");return 0;} printf("%d ",1); for(int x=1;x<=m;++x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!a[i].v) printf("%d ",y-m); } puts(""); } return 0; }
6最长递增子序列
怎么说呢，感觉自己的网络流有刷新了......
这里引入一个分层图的概念,顾名思义,就是一层一层的图呗！这主要体现一种思想,在我们建图时,可以按照题目要求,建立分层图,使得从s到t就是一条合法路径...
针对此题来说,就是我们求一个f数组,表示以i开头的最长递增子序列.显然只有f[i]==ans时,这个点才能是一个序列的起点,我哦们将s向这个点连容量为1的边,之后考虑i的后继,如果b[i]<=b[j]&&f[i]==f[j]+1，此时j才能是i的后继.我们将i向j连边,但同时注意每个店只能用一次,我们拆点限流.即可。第三问,修改与1，n有关的边的容量即可.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=510,M=1010,INF=1e9; int n,b[N],f[N],ans,link[M],tot=1,d[M],current[M],s,t; struct edge{int y,next,v;}a[M*M*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool bfs() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); memcpy(current,link,sizeof(current)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=d[x]+1; q.push(y); if(y==t) return true; } } return false; } inline int dinic(int x,int flow) { if(x==t) return flow; int rest=flow,k; for(int i=current[x];i&&rest;i=a[i].next) { current[x]=i; int y=a[i].y; if(d[y]==d[x]+1&&a[i].v) { k=dinic(y,min(rest,a[i].v)); a[i].v-=k; a[i^1].v+=k; rest-=k; } } return flow-rest; } int main() { freopen("1.in","r",stdin); n=read(); for(int i=1;i<=n;++i) b[i]=read(); for(int i=n;i>=1;--i) { for(int j=i+1;j<=n;++j) if(b[j]>=b[i]) f[i]=max(f[i],f[j]); f[i]++; ans=max(ans,f[i]); } printf("%d ",ans); s=0;t=n<<1|1; for(int i=1;i<=n;++i) { if(f[i]==ans) add(s,i,INF); for(int j=i+1;j<=n;++j) if(b[i]<=b[j]&&f[i]==f[j]+1) add(i+n,j,1); if(f[i]==1) add(i+n,t,1); add(i,i+n,1); } int maxflow=0,flow; while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; printf("%d ",maxflow); memset(link,0,sizeof(link)); memset(a,0,sizeof(a));tot=1; if(n==1) {puts("1");return 0;} for(int i=1;i<=n;++i) { if(f[i]==ans) { if(i!=1) add(s,i,1); else add(s,1,INF); } for(int j=i+1;j<=n;++j) if(b[i]<=b[j]&&f[i]==f[j]+1) add(i+n,j,1); if(f[i]==1) { if(i!=n) add(i+n,t,1); else add(i+n,t,INF); } if(i!=1&&i!=n) add(i,i+n,1); else add(i,i+n,INF); } maxflow=0; while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; printf("%d ",maxflow); return 0; }
7试题库
傻逼题,题意感觉好懵,结果没看懂题意,错想了老长时间了.....
我觉得题意里面应该加一句：每道题只能应用于一个类型.这样就一目了然了,经典的匹配问题一个问题能匹配多个类型，而每个类型都有限制.那我们直接将类型连汇,容量为限制.问题连类型,容量为1,跑最大流即可.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2050,INF=1e9; int link[N],tot=1,d[N],current[N],n,k,s,t; struct edge{int y,v,next;}a[N*N*2]; vector<int>v[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool bfs() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); memcpy(current,link,sizeof(current)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=d[x]+1; q.push(y); if(y==t) return true; } } return false; } inline int dinic(int x,int flow) { if(x==t) return flow; int rest=flow,k; for(int i=current[x];i&&rest;i=a[i].next) { current[x]=i; int y=a[i].y; if(d[y]==d[x]+1&&a[i].v) { k=dinic(y,min(rest,a[i].v)); a[i].v-=k; a[i^1].v+=k; rest-=k; } } return flow-rest; } int main() { //freopen("1.in","r",stdin); k=read();n=read(); s=0;t=n+k+1; int ans=0; for(int i=1;i<=k;++i) { int x=read(); ans+=x; add(i+n,t,x); } for(int i=1;i<=n;++i) { add(s,i,1); int z=read(); for(int j=1;j<=z;++j) { int x=read(); add(i,x+n,1); } } int maxflow=0,flow; while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; if(maxflow<ans) puts("No Solution!"); else { for(int i=1;i<=n;++i) for(int j=link[i];j;j=a[j].next) { int y=a[j].y; if(y-n<=0) continue; if(!a[j].v) v[y-n].push_back(i); } for(int i=1;i<=k;++i) { printf("%d: ",i); for(int j=0;j<v[i].size();++j) printf("%d ",v[i][j]); puts(""); } } return 0; }
8软件补丁
狗屁网络流,一直想怎么建图,最后还是用dij搞得....
直接将状态压缩,连边跑dij即可.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+1e5,M=110;
int link[N],tot,n,m,B1[M],B2[M],F1[M],F2[M],t[M],vis[N];
ll dis[N];
struct edge{int y,v,next;}a[N*40];
char c[100];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline void add(int x,int y,int v)
{
a[++tot].y=y;
a[tot].v=v;
a[tot].next=link[x];
link[x]=tot;
}
inline void dij()
{
priority_queue<pair<ll,int> >q;
memset(vis,0,sizeof(vis));
for(int i=0;i<1<<n;++i) dis[i]=1e18;
q.push({0,(1<<n)-1});
dis[(1<<n)-1]=0;
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(dis[y]>dis[x]+(ll)a[i].v)
{
dis[y]=dis[x]+(ll)a[i].v;
q.push({-dis[y],y});
}
}
}
}
int main()
{
freopen("1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=m;++i)
{
t[i]=read();
scanf("%s",c+1);
for(int j=1;j<=n;++j)
{
B1[i]<<=1;
B2[i]<<=1;
if(c[j]=='+') B1[i]|=1;
else if(c[j]=='-') B2[i]|=1;
}
scanf("%s",c+1);
for(int j=1;j<=n;++j)
{
F1[i]<<=1;
F2[i]<<=1;
if(c[j]=='-') F1[i]|=1;
else if(c[j]=='+') F2[i]|=1;
}
}
for(int i=0;i<(1<<n);++i)
{
for(int j=1;j<=m;++j)
{
if((B1[j]&i)!=B1[j]||(B2[j]&i)) continue;
int s=i&(~F1[j])|F2[j];
add(i,s,t[j]);
}
}
dij();
printf("%d",dis[0]==1e18?0:dis[0]);
return 0;
}
9数字梯形
感觉和方格取数一模一样......
直接构造分层图即可..
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=3200,M=40,INF=1e9; int link[N],tot=1,m,n,c[M][M],s,t,id[M][M],cnt,ans; int incf[N],pre[N],dis[N],vis[N]; struct edge{int y,next,v,c;}a[N*N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v,int c) { a[++tot].y=y;a[tot].c=c;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].c=-c;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool spfa() { queue<int>q;q.push(s); memset(dis,0xef,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0;vis[s]=1;incf[s]=INF; while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!a[i].v) continue; if(dis[y]<dis[x]+a[i].c) { dis[y]=dis[x]+a[i].c; incf[y]=min(incf[x],a[i].v); pre[y]=i; if(!vis[y]) vis[y]=1,q.push(y); } } } if(dis[t]==0xefefefef) return false; return true; } inline void updata() { int x=t; while(x!=s) { int i=pre[x]; a[i].v-=incf[t]; a[i^1].v+=incf[t]; x=a[i^1].y; } ans+=dis[t]*incf[t]; } inline void subtask1() { s=0;t=cnt*2+1; for(int i=1;i<=n;++i) for(int j=1;j<=m+i-1;++j) { add(id[i][j],id[i][j]+cnt,1,c[i][j]); if(i!=n) { add(id[i][j]+cnt,id[i+1][j],1,0); add(id[i][j]+cnt,id[i+1][j+1],1,0); } else if(i==n) add(id[i][j]+cnt,t,1,0); if(i==1) add(s,id[i][j],1,0); } while(spfa()) updata(); printf("%d ",ans); } inline void subtask2() { memset(a,0,sizeof(a));tot=1; memset(link,0,sizeof(link)); s=0;t=cnt+1; for(int i=1;i<=n;++i) for(int j=1;j<=m+i-1;++j) { if(i!=n) { add(id[i][j],id[i+1][j],1,c[i+1][j]); add(id[i][j],id[i+1][j+1],1,c[i+1][j+1]); } else if(i==n) add(id[i][j],t,INF,0); if(i==1) add(s,id[i][j],1,c[i][j]); } ans=0; while(spfa()) updata(); printf("%d ",ans); } inline void subtask3() { memset(a,0,sizeof(a));tot=1; memset(link,0,sizeof(link)); s=0;t=cnt+1; for(int i=1;i<=n;++i) for(int j=1;j<=m+i-1;++j) { if(i!=n) { add(id[i][j],id[i+1][j],INF,c[i+1][j]); add(id[i][j],id[i+1][j+1],INF,c[i+1][j+1]); } else if(i==n) add(id[i][j],t,INF,0); if(i==1) add(s,id[i][j],1,c[i][j]); } ans=0; while(spfa()) updata(); printf("%d ",ans); } int main() { freopen("1.in","r",stdin); m=read();n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m+i-1;++j) c[i][j]=read(),id[i][j]=++cnt; subtask1(); subtask2(); subtask3(); return 0; }
10运输问题
妥妥的费用流就不多说了....
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=210,INF=1e9; int m,n,s,t,link[N],tot=1,dis[N],incf[N],pre[N],vis[N],ans,st[N],ma[N],b[N][N]; struct edge{int y,v,next,c;}a[N*N*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v,int c) { a[++tot].y=y;a[tot].v=v;a[tot].c=c;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].c=-c;a[tot].next=link[y];link[y]=tot; } inline void init() { for(int i=1;i<=m;++i) st[i]=read(); for(int i=1;i<=n;++i) ma[i]=read(); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) b[i][j]=read(); } inline void prework() { memset(a,0,sizeof(a));tot=1; memset(link,0,sizeof(link)); for(int i=1;i<=m;++i) add(s,i,st[i],0); for(int i=1;i<=n;++i) add(i+m,t,ma[i],0); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) add(i,j+m,INF,b[i][j]); } inline bool spfa(int op) { queue<int>q;q.push(s); memset(vis,0,sizeof(vis)); if(op==1) memset(dis,0x3f,sizeof(dis)); else memset(dis,0xef,sizeof(dis)); dis[s]=0;vis[s]=1;incf[s]=INF; while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!a[i].v) continue; if(op==1) { if(dis[y]>dis[x]+a[i].c) { dis[y]=dis[x]+a[i].c; incf[y]=min(incf[x],a[i].v); pre[y]=i; if(!vis[y]) vis[y]=1,q.push(y); } } else { if(dis[y]<dis[x]+a[i].c) { dis[y]=dis[x]+a[i].c; incf[y]=min(incf[x],a[i].v); pre[y]=i; if(!vis[y]) vis[y]=1,q.push(y); } } } } if(op==1&&dis[t]==0x3f3f3f3f) return false; else if(op==2&&dis[t]==0xefefefef) return false; return true; } inline void updata() { int x=t; while(x!=s) { int i=pre[x]; a[i].v-=incf[t]; a[i^1].v+=incf[t]; x=a[i^1].y; } ans+=dis[t]*incf[t]; } int main() { freopen("1.in","r",stdin); m=read();n=read(); s=0;t=m+n+1; init(); prework();ans=0; while(spfa(1)) updata(); printf("%d ",ans); prework();ans=0; while(spfa(2)) updata(); printf("%d ",ans); return 0; }
11最长 k 可重区间集
似乎一看题目便知道要搞什么幺儿子..
首先我们可以发现因为每个点的最多覆盖限制为k,所以我们想到如果选一条线段就将线段上的所有的点覆盖次数减1。
之后我们考虑用网络流做这道题.（网络流擅长做各种限流题...）我们还可以想象成匹配,每个点最多与k个线段匹配.可是如果选一条线段的话,我们需要将这个区间都覆盖一遍.这个是就是典型的一流对多流的问题.
一般的做法是将需要区间覆盖的东西串联起来.如果选线段的话,就从起点到终点连边.这是常规套路.
之后我们考虑在这道题上如何做.
我们将所有的端点离散化,串联起来.考虑每个点都有一个k的限制我们如果在这个网络里体现。
对于限制,一般都与s或t有关。我们假设将限制与t建立起联系。也就是每个点都向t连一条容量为k的边.这时我们思考如果选一条线段如何统计答案。显然如果我们选一条线段需要将区间中的每个点都流1的流，这杨统计答案.可这样显然很难实现..
那我们将限制与s相关联。我们从源点向第一个点连容量为k的边.表示你最多这么多流.之后我们只要考虑将区间都少流1的流即可.那我们直接从起点到终点连容量为1的边即可.费用为长度.考虑不用线段的话,相当于这个点到下一个点没有阻碍,所以我们直接从每一个点都想下一个点连容量为k的边就行.这里注意从源点到汇点的最大流一定是k,因为途中并没有流的丢失...所以我们直接跑最大流最大费用即可.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1010,INF=1e9; int link[N],tot=1,s,t,n,k,b[N],cnt; int ans,dis[N],vis[N],incf[N],pre[N]; struct node{int x,y;}d[N],raw[N]; struct edge{int y,v,c,next;}a[N*N*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline int find(int x){return lower_bound(b+1,b+cnt+1,x)-b;} inline void add(int x,int y,int v,int c) { a[++tot].y=y;a[tot].c=c;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].c=-c;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool spfa() { queue<int>q;q.push(s); memset(dis,0xef,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0;vis[s]=1;incf[s]=INF; while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!a[i].v) continue; if(dis[y]<dis[x]+a[i].c) { dis[y]=dis[x]+a[i].c; incf[y]=min(incf[x],a[i].v); pre[y]=i; if(!vis[y]) vis[y]=1,q.push(y); } } } if(dis[t]==0xefefefef) return false; return true; } inline void updata() { int x=t; while(x!=s) { int i=pre[x]; a[i].v-=incf[t]; a[i^1].v+=incf[t]; x=a[i^1].y; } ans+=dis[t]*incf[t]; } int main() { freopen("1.in","r",stdin); n=read();k=read(); for(int i=1;i<=n;++i) { d[i].x=read(); d[i].y=read(); b[++cnt]=d[i].x; b[++cnt]=d[i].y; } sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-b-1; for(int i=1;i<=n;++i) raw[i].x=find(d[i].x),raw[i].y=find(d[i].y); s=0;t=cnt+1; for(int i=1;i<=cnt;++i) { if(i==cnt) add(i,t,k,0); else { if(i==1) add(s,i,k,0); add(i,i+1,k,0); } for(int j=1;j<=n;++j) if(raw[j].x==i) add(i,raw[j].y,1,d[j].y-d[j].x); } while(spfa()) updata(); printf("%d",ans); return 0; }
例题：
[NOI2008]志愿者招募
刁钻的好题目啊！..
首先我们可以直观地发现这也是一个典型的一流对多流的题目.
考虑每个志愿者我们将从Si到Ti连一条容量为INF,费用为c[i]的边。之后考虑怎么讲每个点的限制加进去.仔细观察这个题中每个点的限制,我们发现是每个点的必须>=a[i]。由于我们用志愿者其实是帮助一个点流出流量的..所以我们可以大致的判断我们需要每个点从志愿者这个途径流出的量>=a[i]。这样我们就可从(i,i+1)这条边做文章了.这样我们考虑设一个基准，由于网络流中每个点流量守恒，及流入多少一定流出多少.我们考虑第一个用志愿者的日子,加入这个点流入INF，那么我们向下一个点流入INF-a[i]，这样就导致至少有a[i]的流从志愿者的途径流.倘若流入的不是INF,那不就失效了吗？不,如过流入的不是INF,那说明前面一定分流了。那我们直接将这些流量,从INF-a[i]流出。倘若有的流流不出了,那说明用志愿者的太少了.这里我们将志愿者用超过容量的流量比作.因为思考我们串联的本质。
我们是将志愿者直接从s连到t的,也就是说他们跨国过的点都是享受到有志愿者的感受(爽).考虑他们少了流就是他们享受的志愿者.之后考虑我们怎么强制这些点少流流量.有一个办法就是我们强制给他们塞一些流量。之后他们向下一个点的容量为INF-a[i],这样他们牛必须通过其他途径少流这些流量。这样就是我们的目的也达成了.
之后我们将s与1连边,n向t连边...跑最大流即可.
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1010,INF=1e9; int link[N],tot=1,n,m,s,t,ans; int dis[N],vis[N],pre[N],incf[N]; struct edge{int y,v,next,c;}a[N*N*2]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v,int c) { a[++tot].y=y;a[tot].c=c;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].c=-c;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline bool spfa() { queue<int>q;q.push(s); memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0;vis[s]=1;incf[s]=INF; while(!q.empty()) { int x=q.front();q.pop();vis[x]=0; for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(!a[i].v) continue; if(dis[y]>dis[x]+a[i].c) { dis[y]=dis[x]+a[i].c; incf[y]=min(incf[x],a[i].v); pre[y]=i; if(!vis[y]) vis[y]=1,q.push(y); } } } if(dis[t]==0x3f3f3f3f) return false; return true; } inline void updata() { int x=t; while(x!=s) { int i=pre[x]; a[i].v-=incf[t]; a[i^1].v+=incf[t]; x=a[i^1].y; } ans+=incf[t]*dis[t]; } int main() { freopen("1.in","r",stdin); n=read();m=read(); s=0;t=n+1; for(int i=1;i<=n;++i) { if(i==1) add(s,i,INF,0); int x=read(); add(i,i+1,INF-x,0); } for(int i=1;i<=m;++i) { int x=read(),y=read(),v=read(); add(x,y+1,INF,v); } while(spfa()) updata(); printf("%d",ans); return 0; }
[CTSC1999]家园 / 星际转移问题
//这道毒瘤网络流的题目...
//让我们在打代码之前先理清思路,争取一次就过..
//首先有人数,求最短时间,我们第一思路就是费用流,但转念一想,费用流对应的是一流一代价,但题目的要求确是一艘飞船
//可以载h[i]个人,但带来的代价确实1,也就是说多个人才造成这1的代价,这不符合费用流的设定,所以我们暂时将费用流
//pass掉...那接着考虑,我们发现这个题目的模型求人数非常符合最大流的设定,但时间就是我们要思考的问题.
//之后我们又发现数据貌似很小,(嗯，你没看错).这启示我们枚举答案, 用最大流来判断答案是否可靠..
//接下来我们按照时间顺序搞事情,直到当前的月球上有超过k个人为止...
//t时刻.我们可以计算出每一艘飞船下一站目的地并连边,且将每一个空间站t-1的时刻向t时刻连边.
//另外如果下一站是地球的话,我们在另用s向它连容量为INF的边,如果是月球的话,我们从他另向t连容量为t的边.
//这道毒瘤网络流的题目... //让我们在打代码之前先理清思路,争取一次就过.. //首先有人数,求最短时间,我们第一思路就是费用流,但转念一想,费用流对应的是一流一代价,但题目的要求确是一艘飞船 //可以载h[i]个人,但带来的代价确实1,也就是说多个人才造成这1的代价,这不符合费用流的设定,所以我们暂时将费用流 //pass掉...那接着考虑,我们发现这个题目的模型求人数非常符合最大流的设定,但时间就是我们要思考的问题. //之后我们又发现数据貌似很小,(嗯，你没看错).这启示我们枚举答案, 用最大流来判断答案是否可靠.. //接下来我们按照时间顺序搞事情,直到当前的月球上有超过k个人为止... //t时刻.我们可以计算出每一艘飞船下一站目的地并连边,且将每一个空间站t-1的时刻向t时刻连边. //另外如果下一站是地球的话,我们在另用s向它连容量为INF的边,如果是月球的话,我们从他另向t连容量为t的边. #include<bits/stdc++.h> #define ll long long using namespace std; const int N=14,M=21,INF=1e9,maxn=2e5+10; int link[maxn],tot=1,d[maxn],current[maxn],s,t; int n,m,k,r[M],h[M],c[M][N],id[N+2][300010],f[N]; struct edge{int y,v,next;}a[maxn*60]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot; } inline int getf(int k){return f[k]==k?k:f[k]=getf(f[k]);} inline void merge(int x,int y) { int t1=getf(x),t2=getf(y); if(t1!=t2) f[t1]=t2; } inline bool bfs() { queue<int>q;q.push(s); memset(d,0,sizeof(d)); memcpy(current,link,sizeof(current)); d[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(d[y]||!a[i].v) continue; d[y]=d[x]+1; q.push(y); if(y==t) return true; } } return false; } inline int dinic(int x,int flow) { if(x==t) return flow; int rest=flow,k; for(int i=current[x];i&&rest;i=a[i].next) { current[x]=i; int y=a[i].y; if(d[y]==d[x]+1&&a[i].v) { k=dinic(y,min(rest,a[i].v)); if(!k) d[y]=-1; a[i].v-=k; a[i^1].v+=k; rest-=k; } } return flow-rest; } int main() { // freopen("1.in","r",stdin); n=read();m=read();k=read(); for(int i=1;i<=n+2;++i) f[i]=i; for(int i=1;i<=m;++i) { h[i]=read();r[i]=read(); for(int j=1;j<=r[i];++j) { c[i][j]=read(); if(c[i][j]==0) c[i][j]=n+1; else if(c[i][j]==-1) c[i][j]=n+2; } } for(int i=1;i<=m;++i) for(int j=1;j<=r[i];++j) { if(j==r[i]) merge(c[i][r[i]],c[i][1]); else merge(c[i][j],c[i][j+1]); } if(getf(n+1)!=getf(n+2)) {puts("0");return 0;} int maxflow=0,flow; int T=0; s=0;t=1;int cnt=2; for(int i=1;i<=n+2;++i) id[i][T]=++cnt; add(s,id[n+1][T],INF);add(id[n+2][T],t,INF); while(++T) { for(int i=1;i<=n+2;++i) id[i][T]=++cnt; for(int i=1;i<=n;++i) add(id[i][T-1],id[i][T],INF); add(s,id[n+1][T],INF);add(id[n+2][T],t,INF); for(int i=1;i<=m;++i) { int l=T%r[i]; if(!l) add(id[c[i][r[i]]][T-1],id[c[i][1]][T],h[i]); else add(id[c[i][l]][T-1],id[c[i][l+1]][T],h[i]); } while(bfs()) while(flow=dinic(s,INF)) maxflow+=flow; if(maxflow>=k) break; } printf("%d",T); return 0; }