开始刷网络流24题，在此记录 题目列表 题库 - LibreOJ (loj.ac)
|
问题编号 |
问题名称 |
问题模型 |
转化模型 |
|
1 |
飞行员配对方案问题 |
二分图最大匹配 |
网络最大流 |
|
2 |
太空飞行计划问题 |
最大权闭合图 |
网络最小割 |
|
3 |
最小路径覆盖问题 |
有向无环图最小路径覆盖 |
网络最大流 |
|
4 |
魔术球问题 |
有向无环图最小路径覆盖 |
网络最大流 |
|
5 |
圆桌问题 |
二分图多重匹配 |
网络最大流 |
|
6 |
最长递增子序列问题 |
最多不相交路径 |
网络最大流 |
|
7 |
试题库问题 |
二分图多重匹配 |
网络最大流 |
|
8 |
机器人路径规划问题 |
(未解决) |
最小费用最大流 |
|
9 |
方格取数问题 |
二分图点权最大独立集 |
网络最小割 |
|
10 |
餐巾计划问题 |
线性规划网络优化 |
最小费用最大流 |
|
11 |
航空路线问题 |
最长不相交路径 |
最小费用最大流 |
|
12 |
软件补丁问题 |
最小转移代价 |
最短路径 |
|
13 |
星际转移问题 |
网络判定 |
网络最大流 |
|
14 |
孤岛营救问题 |
分层图最短路径 |
最短路径 |
|
15 |
汽车加油行驶问题 |
分层图最短路径 |
最短路径 |
|
16 |
数字梯形问题 |
最大权不相交路径 |
最小费用最大流 |
|
17 |
运输问题 |
网络费用流量 |
最小费用最大流 |
|
18 |
分配问题 |
二分图最佳匹配 |
最小费用最大流 |
|
19 |
负载平衡问题 |
最小代价供求 |
最小费用最大流 |
|
20 |
深海机器人问题 |
线性规划网络优化 |
最小费用最大流 |
|
21 |
最长k可重区间集问题 |
最大权不相交路径 |
最小费用最大流 |
|
22 |
最长k可重线段集问题 |
最大权不相交路径 |
最小费用最大流 |
|
23 |
火星探险问题 |
线性规划网络优化 |
最小费用最大流 |
|
24 |
骑士共存问题 |
二分图最大独立集 |
网络最小割 |
1.飞行员配对方案问题
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 10001 #define M 100001 using namespace std;int f,p,k,n,m,x,y,z;char c; int read() { f=0;p=1; while(c=getchar(),c<=47||c>=58) if(c=='-') p=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48; return p*f; } struct node{int next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; e[tot].next=l[v];e[tot].to=u;e[tot].w=0;l[v]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,2147483647); return r; } int main() { memset(l,-1,sizeof(l));//多了这一行 s=0; cin>>m>>n; t=m+n+1; for(int i=1;i<=m;i++){ addE(s,i,1); addE(i,s,0); } for(int i=m+1;i<=n+m;i++){ addE(i,t,1); addE(t,i,0); } int x,y; while(cin>>x>>y){ if(x==-1)break; addE(x,y,1); addE(y,x,0); } int ans=dinic(); cout<<ans<<endl; if(ans==0){ cout<<"No Solution!"<<endl; return 0; } for(int i=m+1;i<=n+m;i++) for(int j=l[i];~j;j=e[j].next) if(e[j].to!=t&&e[j].w==1) printf("%d %d ",e[j].to,i); }
2.太空飞行计划问题
这个题是最大权闭合图的模板题。答案是所有实验的总收益-最小割。其中最小割==最大流。下图为建图方式。这个图中的最小割。
割==花费。先假设要获得所有实验的收益，求最小割后如果某个实验被割掉，代表他的收入小于代价，这个实验不做。器材被割掉，代表使用这个器材能获得更小的割。
比如割在（器材->T）的边上，那么相当于相关实验的收入可以覆盖这个器材的花费。可以割掉。
再比如说割在（S->实验）的边上，相当于做实验的钱都花在器材身上。
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 50001 #define M 1000001 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,1e9+7); return r; } vector<int>v[450]; inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } int main() { memset(l,-1,sizeof(l));//多了这一行 s=0; cin>>m>>n; int sum=0; t=m+n+1; ll ans=0; for(int i=1;i<=m;i++){ int c; cin>>c; ans+=c; addE(s,i,c); addE(i,s,0); int t=1; while(t){ t=read(c); //cout<<c<<endl; addE(i,c+m,inf); addE(c+m,i,0); } } for(int i=1;i<=n;i++){ int c; cin>>c; addE(i+m,t,c); addE(t,i+m,0); } //cout<<ans<<endl; ans-=dinic(); for(int i=1;i<=m;i++){ if(d[i]>0)cout<<i<<" "; } cout<<endl; for(int i=1;i<=n;i++){ if(d[m+i]>0)cout<<i<<" "; } cout<<endl; cout<<ans<<endl; }
3.最小路径覆盖问题
原图每个点拆为两份。每个点和与自己相连的被拆分点连接，求最大匹配。最小路径覆盖=原图的结点数-新图的最大匹配数。
一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 50001 #define M 1000001 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,1e9+7); return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } vector<int>v[450]; int vis[450]; void dfs(int u){ if(vis[u])return ; vis[u]=1; cout<<u<<" "; for(auto i:v[u]){ dfs(i); } } int main() { memset(l,-1,sizeof(l));//多了这一行 s=0; cin>>n>>m; t=2*n+1; ll ans=n; for(int i=1;i<=m;i++){ ll u,v; cin>>u>>v; addE(u,v+n,1); addE(v+n,u,0); } for(int i=1;i<=n;i++){ addE(s,i,1); addE(i,s,0); } for(int i=1+n;i<=n*2;i++){ addE(i,t,1); addE(t,i,0); } ans-=dinic(); for(int i=n+1;i<=2*n;i++){ for(int j=l[i];~j;j=e[j].next){ if(e[j].to!=t&&e[j].w){ v[e[j].to].push_back(i-n); } } } for(int i=1;i<=n;i++){ if(vis[i])continue; dfs(i); cout<<endl; } cout<<ans<<endl; }
4.魔术球问题
二分+最小路径覆盖。建图方式为对于当前二分值x，即共有x个数字，每个数字和与自己能组成完全平方数的数字建边，跑最大匹配。即求最小路径覆盖。每一个路径上的点放在一个容器内即可。但鬼畜的是，这个代码在洛谷上只用了500ms 在swust上t了。不管了。
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 3300 #define M 25000 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,1e9+7); return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } vector<int>v[10005]; int vis[10005]; void dfs(int u){ if(vis[u])return ; vis[u]=1; cout<<u<<" "; for(auto i:v[u]){ dfs(i); } } int wan[1000005]; bool check(int x){ memset(l,-1,sizeof(l));//多了这一行 tot=0; memset(d,0,sizeof(d)); s=0; t=x*2+1; for(int i=1;i<=x;i++){ addE(s,i,1); addE(i,s,0); } for(int i=1;i<=x;i++){ for(int j=i+1;j<=x;j++){ if(wan[i+j]){ addE(i,j+x,1); addE(j+x,i,0); } } } for(int i=x+1;i<=2*x;i++){ addE(i,t,1); addE(t,i,0); } ll res=x; res-=dinic(); if(res<=n)return true; return false; } int main(){ for(int i=1;i<=1000;i++){ wan[i*i]=1; } cin>>n; ll ls=n,r=1600; int ans=0; while(ls<=r){ ll mid=(ls+r)/2; if(check(mid)){ ans=mid; for(int i=1;i<=mid;i++)v[i].clear(); for(int i=mid+1;i<=2*mid;i++){ for(int j=l[i];~j;j=e[j].next){ if(e[j].to!=t&&e[j].w){ v[e[j].to].push_back(i-mid); } } } ls=mid+1; } else{ r=mid-1; } } cout<<ans<<endl; for(int i=1;i<=ans;i++){ if(vis[i])continue; dfs(i); cout<<endl; } return 0; }
5.圆桌问题
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 50001 #define M 1000001 using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,2147483647); return r; } vector<int>v[450]; int main() { memset(l,-1,sizeof(l));//多了这一行 s=0; cin>>m>>n; int sum=0; t=m+n+1; for(int i=1;i<=m;i++){ int c; cin>>c; sum+=c; addE(s,i,c); addE(i,s,0); for(int j=m+1;j<=n+m;j++){ addE(i,j,1); addE(j,i,0); } } for(int i=m+1;i<=n+m;i++){ int c; cin>>c; addE(i,t,c); addE(t,i,0); } int ans=dinic(); if(ans!=sum){ cout<<0<<endl; return 0; } else { cout<<1<<endl; } for(int i=m+1;i<=m+1+n;i++){ for(int j=l[i];j!=-1;j=e[j].next){ if(e[j].to!=t&&e[j].w){ v[e[j].to].push_back(i-m); } } } for(int i=1;i<=m;i++){ for(auto sp:v[i]){ cout<<sp<<" "; } cout<<endl; } }
6.最长递增子序列
这是个最多不相交路径问题。建图不是很好想，把一个点拆成两个，每个点被拆出来的点与序列中大于等于他的那个节点的未拆开的部分相连，也就是他的下一个结点。最后，所有深度为最长递增子序列长度的结点与t相连。所有深度为1的结点与s相连。如图所示。对于数组 3 2 5 4 （图中数组为下标）
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 3300 #define M 25000 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs() { memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(e[i].w&&d[y]==-1) { d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow) { if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next) { int y=e[i].to; if(d[x]+1==d[y]&&e[i].w) { f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) r+=dfs(s,1e9+7); return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } ll a[505]; ll dp[505]; void solve(){ memset(l,-1,sizeof(l)); ll ns; cin>>ns; for(int i=1;i<=ns;i++){ cin>>a[i]; } ll maxn=1; for(int i=1;i<=ns;i++){ dp[i]=1; } for(int i=1;i<=ns;i++){ for(int j=1;j<i;j++){ if(a[j]<=a[i]){ dp[i]=max(dp[i],dp[j]+1); maxn=max(maxn,dp[i]); } } } if(maxn==1){ cout<<1<<endl<<ns<<endl<<ns<<endl; return ; } s=0; t=ns*2+1; cout<<maxn<<endl; for(int i=1;i<=ns;i++){ if(dp[i]==1){ addE(s,i,1); addE(i,s,0); } if(dp[i]==maxn){ addE(i+ns,t,1); addE(t,i+ns,0); } } for(int i=1;i<=ns;i++){ for(int j=1;j<=ns;j++){ if(i==j){ addE(i,j+ns,1); addE(j+ns,i,0); continue; } if(dp[i]==dp[j]+1&&i>j&&a[j]<=a[i]){ addE(j+ns,i,1); addE(i,j+ns,0); } } } ll ans=dinic(); cout<<ans<<endl; tot=0; memset(l,-1,sizeof(l)); for(int i=1;i<=ns;i++){ if(dp[i]==1){ if(i==1){ addE(s,i,0x3f3f3f3f3f3f3f3f3f); } else addE(s,i,1); addE(i,s,0); } if(dp[i]==maxn){ if(i==ns){ addE(i+ns,t,0x3f3f3f3f3f3f3f3f3f); } else addE(i+ns,t,1); addE(t,i+ns,0); } } for(int i=1;i<=ns;i++){ for(int j=1;j<=ns;j++){ if(i==j){ if(i==1||i==ns){ addE(i,j+ns,0x3f3f3f3f3f3f3f3f3f3f3f); } else addE(i,j+ns,1); addE(j+ns,i,0); continue; } if(dp[i]==dp[j]+1&&i>j&&a[j]<=a[i] ){ addE(j+ns,i,1); addE(i,j+ns,0); } } } ans=dinic(); cout<<ans<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
7.试题库
我想这是个简单题，就不说了
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 3300 #define M 100005 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()){ int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(e[i].w&&d[y]==-1){ d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow){ if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(d[x]+1==d[y]&&e[i].w){ f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) { r+=dfs(s,1e9+7); } return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } vector<int>v[205]; void solve(){ memset(l,-1,sizeof(l)); cin>>k>>n; s=0; t=n+k+1; ll sum=0; for(int i=1;i<=k;i++){ ll x; cin>>x; sum+=x; addE(i+n,t,x); addE(t,i+n,0); } for(int i=1;i<=n;i++){ ll nu; cin>>nu; for(int j=1;j<=nu;j++){ ll te; cin>>te; addE(i,n+te,1); addE(n+te,i,0); } addE(s,i,1); addE(i,s,0); } ll ans=dinic(); if(ans!=sum){ cout<<"No Solution!"<<endl; return ; } for(int i=1;i<=k;i++){ for(int j=l[i+n];~j;j=e[j].next){ if(e[j].to!=t&&e[j].w){ v[i].push_back(e[j].to); } } } for(int i=1;i<=k;i++){ cout<<i<<": "; if(v[i].size()==0){ cout<<endl; continue; } for(int j=0;j<v[i].size()-1;j++){ cout<<v[i][j]<<" "; } cout<<v[i][v[i].size()-1]; cout<<endl; } } int main(){ int tt=1; while(tt--){ solve(); } }
9.方格取数
这个题因为把汇点设为了1 ，很久没找出来bug，下次注意。是一个最小点覆盖的模板题。当然这个题要求的是最大独立集合==点权和-最小点覆盖。最小点覆盖为按照如下方式建边的最小割。
- 所有黑色方格与源点建一条流量为方格中数字的边。
- 所有白色方格与汇点建立一条流量为方格中数字的边。
- 所有黑色的方格与其四联通的白色方格建立一条流量为$+∞$的边。
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 3300 #define M 100005 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()){ int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(e[i].w&&d[y]==-1){ d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow){ if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(d[x]+1==d[y]&&e[i].w){ f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) { r+=dfs(s,1e9+7); } return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } ll a[55][55]; void solve(){ memset(l,-1,sizeof(l)); ll ans=0; s=0; cin>>m>>n; t=n*m+1; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; ans+=a[i][j]; if((i+j)%2==0){ addE(s,(i-1)*n+j,a[i][j]); addE((i-1)*n+j,s,0); } else{ addE((i-1)*n+j,t,a[i][j]); addE(t,(i-1)*n+j,0); } } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if((i+j)%2==0){ if(j<n){ addE((i-1)*n+j,(i-1)*n+j+1,inf); addE((i-1)*n+j+1,(i-1)*n+j,0); } if(i<m){ addE((i-1)*n+j,(i)*n+j,inf); addE(i*n+j,(i-1)*n+j,0); } if(i>1){ addE((i-1)*n+j,(i-2)*n+j,inf); addE((i-2)*n+j,(i-1)*n+j,0); } if(j>1){ addE((i-1)*n+j,(i-1)*n+j-1,inf); addE((i-1)*n+j-1,(i-1)*n+j,0); } } } } ans-=dinic(); cout<<ans<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
10.餐巾计划
如图建图，跑费用流即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { // cout<<1<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } } // namespace MCMF ll a[100005]; void solve(){ int inf=0x3f3f3f3f3f3f; ll n,p,m,f,ns,s; cin>>n>>p>>m>>f>>ns>>s; ll ss=0; ll tt=n*3+1; for(int i=1;i<=n;i++){ ll c; cin>>c; MCMF::addEdge(ss,i+n,c,0); MCMF::addEdge(ss,i,inf,p); MCMF::addEdge(i,tt,c,0); MCMF::addEdge(i+n,i+n+1,inf,0); if(i+m<=n) MCMF::addEdge(i+n,i+m,inf,f); if(i+ns<=n){ MCMF::addEdge(i+n,i+ns,inf,s); } } MCMF::run(ss,tt); cout<<MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
11.航空路线问题
其实等于从 1 走到点 n 走两次。
由于每个点只能走一次，很容易想到拆点（下面称拆出来的两个点为出点和入点），然后中间连一条流量为 1 的边，由于要求点数最大，所以这条边上再加一个 1 的费用。对于其他的边 ( x , y ) ，连一条由 x 的出点到 y 的入点的边，流量为 1 ，费用为 0 。然后跑一次费用流即可。
建图方法和最多不相交路径数类似，只不过加了个最长的要求，所以改用费用流。给每个点自己的连边加上一个费用。
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { // cout<<1<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } } // namespace MCMF ll n,m; ll a[100005]; int vis[1005]; map<string ,int>mp; map<int ,string >mps; void dfs1(int x){ // cout<<x<<endl; cout<<mps[x]<<endl; if(x==n)return ; for(int j=MCMF::head[x+n];j;j=MCMF::edges[j].next){ if(MCMF::edges[j].w==0&&!vis[MCMF::edges[j].to]){ vis[MCMF::edges[j].to]=1; dfs1(MCMF::edges[j].to); return ; } } } void dfs2(int x){ if(x==n)return ; for(int j=MCMF::head[x+n];j;j=MCMF::edges[j].next){ if(MCMF::edges[j].w==0&&!vis[MCMF::edges[j].to]){ vis[MCMF::edges[j].to]=1; dfs2(MCMF::edges[j].to); cout<<mps[x]<<endl; return ; } } } void solve(){ int inf=0x3f3f3f3f3f3f; cin>>n>>m; int s=1; int t=n+n; for(int i=1;i<=n;i++){ string x; cin>>x; mp[x]=i; mps[i]=x; } MCMF::addEdge(1,1+n,2,-1); MCMF::addEdge(n,n+n,2,0); for(int i=2;i<n;i++){ MCMF::addEdge(i,i+n,1,-1); } for(int i=1;i<=m;i++){ string u,v; cin>>u>>v; if(mp[u]>mp[v]){ swap(u,v); } if(mp[u]==1&&mp[v]==n){ MCMF::addEdge(mp[u]+n,mp[v],1,0); } MCMF::addEdge(mp[u]+n,mp[v],1,0); } MCMF::run(s,t); if(MCMF::maxflow!=2){ cout<<"No Solution!"<<endl; return ; } cout<<-(MCMF::mincost)<<endl; dfs1(1); vis[n]=0; dfs2(1); } int main(){ int tt=1; while(tt--){ solve(); } }
12.软件补丁
不明白为什么会在网络流24题里面，但是仍然是一个很有意思的题目，也很有启发。考虑状态压缩。然后跑dij。这里状态的每一位就代表一个漏洞。而跑的过程中要在dij里面判断下一个状态。道理自然是不能全都建边，因为不是每个状态都能到达。
然后就考虑n非常小，所以状压表示。
然后这里建边显然是不合理的所以对于每个点都需要扫一遍看这条边能不能连出去。然后转移就好了。
具体操作都在dij里面，复习的时候有不明白可以看看。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; const int N=200005; int prime[1100000],primesize; bool isprime[11000000]; ll f[N],invf[N]; ll inv[N]; void getlist(int listsize){ memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++){ if(isprime[i])prime[++primesize]=i; for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) break; } } } void extend_gcd(ll a, ll b, ll& d, ll& x, ll& y) { if(!b){ d = a; x = 1; y = 0; } else { extend_gcd(b, a%b,d, y, x); y -= x*(a/b);} } void ni(int n) { inv[0] = inv[1] = 1; for(int i = 2; i <= n; i++) { inv[i] = (mod - (mod/i))*inv[mod%i]%mod; } } ll fpow(ll a,ll k){ ll res=1; while(k){ if(k&1) res=(res*a)%mod; k>>=1; a=a*a%mod; //cout<<1<<endl; } return res; } void init(int n){ f[0]=1; for(int i=1;i<=n;++i){ f[i]=f[i-1]*i%mod; } invf[n]=fpow(f[n],mod-2); for(int i=n-1;i>=0;--i){ invf[i]=invf[i+1]*(i+1)%mod; } } ll C(int n,int k){ if(k<0 || k>n) return 0; return f[n]*invf[k]%mod*invf[n-k]%mod; } priority_queue<pair<int,int> >Q; int dis[1<<20],m; bool vis[1<<20]; struct node{ int b1,b2,f1,f2,cost; bool chk(int x){ return ((x&b1)==b1)&&((x&b2)==0); } int cl(int x){ x^=x&f1; x|=f2; return x; } }a[105]; void dij(int x){ memset(vis,0,sizeof(vis)); memset(dis,63,sizeof(dis)); dis[x]=0; Q.push({0,x}); for(;!Q.empty();){ x=Q.top().second; Q.pop(); if(vis[x])continue; vis[x]=1; if(x==0)return ; for(int i=1;i<=m;i++){ if(a[i].chk(x)){ int to=a[i].cl(x); if(dis[x]+a[i].cost<dis[to]){ dis[to]=dis[x]+a[i].cost; Q.push({-dis[to],to}); } } } } } void solve(){ ll n; cin>>n>>m; ll temp=(1<<n)-1; for(int i=1;i<=m;i++){ ll cost,f1,f2,b1,b2; string s1,s2; f1=f2=b1=b2=0; cin>>cost; cin>>s1>>s2; for(int j=0;j<n;j++){ if(s1[j]=='+')b1|=1<<j; if(s1[j]=='-')b2|=1<<j; if(s2[j]=='-')f1|=1<<j; if(s2[j]=='+')f2|=1<<j; } a[i]={b1,b2,f1,f2,cost}; } dij(temp); if(!vis[0])cout<<0<<endl; else cout<<dis[0]<<endl; } int main(){ ios::sync_with_stdio(false);cin.tie(0); // getlist(1e7); int t=1; // cin>>t; while(t--){ solve(); } }
13.星际转移
经典按照时间线建图，边建图边跑网络流。这里贴一个感觉很精妙的代码。
#include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int n,m,k,h[25],r[25][25]; int head[48000],nex[480000],V[480000],W[480000],las=2,maxflow; bool vis[48000]; inline void addedge(int u,int v,int w) { nex[las]=head[u],V[las]=v,W[las]=w; head[u]=las++; nex[las]=head[v],V[las]=u; head[v]=las++; } int dfs(int now,int low) { if (vis[now]||!low) return 0; if (now==n+1) { maxflow+=low; return low; } vis[now]=true; for (int i=head[now],res; i; i=nex[i]) { res=dfs(V[i],min(low,W[i])); W[i]-=res,W[i^1]+=res; if (res) return res; } return 0; } int main() { cin>>n>>m>>k; for (int i=1; i<=m; ++i) { cin>>h[i]>>r[i][0]; for (int j=1; j<=r[i][0]; ++j) { cin>>r[i][j]; if (r[i][j]==-1) r[i][j]=n+1; } } for (int t=0; t<=750; ++t) { for (int i=0; i<=n; ++i) addedge(i+t*(n+2),i+(t+1)*(n+2),inf); addedge((t+2)*(n+2)-1,(t+1)*(n+2)-1,inf); for (int i=1; i<=m; ++i) addedge(r[i][t%r[i][0]+1]+t*(n+2) ,r[i][(t+1)%r[i][0]+1]+(t+1)*(n+2),h[i]); do {memset(vis,0,sizeof(vis)); } while (dfs(0,inf)); if (maxflow>=k) { cout<<t+1; return 0; } } cout<<0; }
经典代码
#include<cstring> #include<cstdio> #include<queue> #include<bits/stdc++.h> #define min(a,b) a<b?a:b #define N 48000 #define M 480000 typedef long long ll; using namespace std;int f,p,k,n,m,x,y,z;char c; struct node{int from,next,to,w;}e[M<<1];int l[N],tot,d[N],s,t; const int inf=1e9+7; void addE(int u,int v,int w) { e[tot].next=l[u];e[tot].to=v;e[tot].w=w;l[u]=tot++; return; } bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q;d[s]=0;q.push(s); while(q.size()){ int x=q.front();q.pop(); for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(e[i].w&&d[y]==-1){ d[y]=d[x]+1; q.push(y); if(y==t) return true; } } } return false; } int dfs(int x,int flow){ if(x==t) return flow; int rest=0,k; for(int i=l[x];i!=-1;i=e[i].next){ int y=e[i].to; if(d[x]+1==d[y]&&e[i].w){ f=dfs(y,min(flow-rest,e[i].w)); if(!f) d[y]=0; e[i].w-=f;rest+=f;e[i^1].w+=f; } } if(!rest) d[x]=0; return rest; } int dinic() { int r=0; while(bfs()) { r+=dfs(s,1e9+7); } return r; } inline int read(int &x){ char c;x=0; while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return c==' '||c==' '?0:1; } ll r[25][25]; ll v[450]; void solve(){ memset(l,-1,sizeof(l)); cin>>n>>m>>k; s=0; t=n+1; for(int i=1;i<=m;i++){ cin>>v[i]>>r[i][0]; for(int j=1;j<=r[i][0];j++){ cin>>r[i][j]; if(r[i][j]==-1)r[i][j]=n+1; } } ll ff=0; for(int tt=0;tt<=750;tt++){ for(int i=0;i<=n;i++){ addE(i+tt*(n+2),i+(tt+1)*(n+2),inf); addE(i+(tt+1)*(n+2),i+tt*(n+2),0); } addE((tt + 2) * (n + 2) - 1, (tt + 1) * (n + 2) - 1, inf); addE((tt + 1) * (n + 2) - 1, (tt + 2) * (n + 2) - 1, 0); for(int i=1;i<=m;i++){ addE(r[i][tt % r[i][0] + 1] + tt * (n + 2), r[i][(tt + 1) % r[i][0] + 1] + (tt + 1) * (n + 2), v[i]); addE(r[i][(tt + 1) % r[i][0] + 1] + (tt + 1) * (n + 2),r[i][tt % r[i][0] + 1] + tt * (n + 2),0); } t=(tt ) * (n + 2)+n+1; ff+=dinic(); if(ff>=k){ cout<<tt+1<<endl; return ; } } cout<<0<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
14.孤岛营救问题
再次懵逼为何网络流24题会有最短路，而且还是简单的分层bfs
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; map<pair<pair<int,int>,pair<int,int> >,int >mp; int vis[2050][11][11]; vector<int> bao[11][11]; int dx[4]={0,-1,1,0}; int dy[4]={1,0,0,-1}; ll dis[2050][11][11]; ll n,m,p; void bfs(){ queue<pair<int,pair<int,int> > >q; q.push({0,{1,1}}); vis[0][1][1]=1; dis[0][1][1]=0; while(!q.empty()){ auto u=q.front(); q.pop(); vis[u.first][u.second.first][u.second.second]=1; int x=u.second.first; int y=u.second.second; int cnt=u.first; for(int i=0;i<4;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(xx<1||xx>n||yy<1||yy>m)continue; int ct=mp[{{x,y},{xx,yy}}]; if(vis[cnt][xx][yy])continue; if(!ct){ dis[cnt][xx][yy]=min(dis[cnt][xx][yy],dis[cnt][x][y]+1); q.push({cnt,{xx,yy}}); } else{ ct--; if(cnt&(1<<(ct-1))){ dis[cnt][xx][yy]=min(dis[cnt][xx][yy],dis[cnt][x][y]+1); q.push({cnt,{xx,yy}}); } } } if(bao[x][y].size()){ for(auto i:bao[x][y]){ int j=(1<<(i-1)); dis[cnt|j][x][y]=min(dis[cnt|j][x][y],dis[cnt][x][y]); if(!vis[cnt|j][x][y]){ q.push({cnt|j,{x,y}}); } } } } } void solve(){ memset(dis,0x3f,sizeof(dis)); cin>>n>>m>>p; ll k; cin>>k; for(int i=1;i<=k;i++){ ll x1,y1,x2,y2,g; cin>>x1>>y1>>x2>>y2>>g; mp[{{x1,y1},{x2,y2}}]=g+1; mp[{{x2,y2},{x1,y1}}]=g+1; } cin>>k; for(int i=1;i<=k;i++){ ll x,y,q; cin>>x>>y>>q; bao[x][y].push_back(q); } bfs(); ll ans=0x3f3f3f3f3f3f3f; for(int i=0;i<=2049;i++){ ans=min(ans,dis[i][n][m]); } if(ans==0x3f3f3f3f3f3f3f)cout<<-1<<endl; else cout<<ans<<endl; } int main(){ ios::sync_with_stdio(false);cin.tie(0); // getlist(1e7); int t=1; // cin>>t; while(t--){ solve(); } }
15.汽车加油行驶问题
#include<bits/stdc++.h> using namespace std; typedef long long ll; int gs[1005][1005]; int id[2009][2009]; int tot=0; const int maxn=6e5+10; const int inf=0x3f3f3f3f; int n,m; struct node{ int v,w; node(){ } node(int _v,int _w){ v=_v; w=_w; } }; vector <node> g[maxn]; int dst[maxn]; queue <int> qu; int inq[maxn]; void add(int u,int v,int w){ g[u].push_back(node(v,w)); // g[v].push_back(node(u,w)); } void spfa(int s){ memset(dst,inf,sizeof dst); int u=s; dst[u]=0; qu.push(u); inq[u]=1; while(!qu.empty()){ u=qu.front(); qu.pop(); inq[u]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i].v; int w=g[u][i].w; if(dst[v]>dst[u]+w){ dst[v]=dst[u]+w; if(!inq[v]){ qu.push(v); inq[v]=1; } } } } } void solve(){ ll n,k,a,b,c; cin>>n>>k>>a>>b>>c; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ id[i][j]=++tot; cin>>gs[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(gs[i][j]){ int u=id[i][j],v=id[i][j]+n*n; if( j!=n ) add( u,v+1,0 ); if( j!=1 ) add( u,v-1,b ); if( i!=1 ) add( u,v-n,b ); if( i!=n ) add( u,v+n,0 ); for(int q=1;q<=k;q++) add( u+q*n*n,u,a ); continue; } for(int q=1;q<=k;q++) { int u=id[i][j]+(q-1)*n*n,v=id[i][j]+q*n*n; if( j!=n ) add( u,v+1,0 ); if( j!=1 ) add( u,v-1,b ); if( i!=1 ) add( u,v-n,b ); if( i!=n ) add( u,v+n,0 ); add(u,id[i][j],c+a); if( q==k ) add(v,id[i][j],c+a); } } } spfa(1); int minn=1e9; for(int i=1;i<=k+1;i++){ minn=min(dst[i*n*n],minn); } cout<<minn; } int main(){ ios::sync_with_stdio(false);cin.tie(0); // getlist(1e7); int t=1; // cin>>t; while(t--){ solve(); } }
16.数字梯形
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init(){ memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq)); memset(cur,0,sizeof(cur));maxflow=0; mincost=0; cnt=1; } } // namespace MCMF ll ti[250][250]; ll get(int i,int j,int k){ return i*100+j*2+k; } void solve(){ int inf=0x3f3f3f3f3f3f; ll n,m; cin>>m>>n; int s=0; int t=9000; for(int i=0;i<n;i++){ for(int j=1;j<=m+i;j++){ cin>>ti[i][j]; } } for(int j=1;j<=m;j++){ MCMF::addEdge(s,get(0,j,0),1,0); } for(int i=0;i<=n-1;i++){ for(int j=1;j<=m+i;j++){ MCMF::addEdge(get(i,j,0),get(i,j,1),1,-ti[i][j]); MCMF::addEdge(get(i,j,1),get(i+1,j,0),1,0); MCMF::addEdge(get(i,j,1),get(i+1,j+1,0),1,0); } } for(int j=1;j<m+n;j++){ MCMF::addEdge(get(n-1,j,1),t,1,0); } MCMF::run(s,t); //cout<<MCMF::maxflow<<endl; cout<<-MCMF::mincost<<endl; MCMF::init(); for(int j=1;j<=m;j++){ MCMF::addEdge(s,get(0,j,0),1,0); } for(int i=0;i<=n-1;i++){ for(int j=1;j<=m+i;j++){ MCMF::addEdge(get(i,j,0),get(i,j,1),100,-ti[i][j]); MCMF::addEdge(get(i,j,1),get(i+1,j,0),1,0); MCMF::addEdge(get(i,j,1),get(i+1,j+1,0),1,0); } } for(int j=1;j<m+n;j++){ MCMF::addEdge(get(n-1,j,1),t,100,0); } MCMF::run(s,t); //cout<<MCMF::maxflow<<endl; cout<<-MCMF::mincost<<endl; MCMF::init(); for(int j=1;j<=m;j++){ MCMF::addEdge(s,get(0,j,0),1,0); } for(int i=0;i<=n-1;i++){ for(int j=1;j<=m+i;j++){ MCMF::addEdge(get(i,j,0),get(i,j,1),100,-ti[i][j]); MCMF::addEdge(get(i,j,1),get(i+1,j,0),100,0); MCMF::addEdge(get(i,j,1),get(i+1,j+1,0),100,0); } } for(int j=1;j<m+n;j++){ MCMF::addEdge(get(n-1,j,1),t,100,0); } MCMF::run(s,t); //cout<<MCMF::maxflow<<endl; cout<<-MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
17.运输问题
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init(){ memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq)); memset(cur,0,sizeof(cur));maxflow=0; mincost=0; cnt=1; } } // namespace MCMF ll numi[105]; ll numj[105]; ll c[105][105]; void solve(){ int inf=0x3f3f3f3f3f3f; ll n,m; cin>>m>>n; int s=0; int t=1000; for(int i=1;i<=m;i++){ cin>>numi[i]; MCMF::addEdge(s,i,numi[i],0); } for(int i=1;i<=n;i++){ cin>>numj[i]; MCMF::addEdge(m+i,t,numj[i],0); } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>c[i][j]; //cout<<c<<endl; MCMF::addEdge(i,j+m,inf,c[i][j]); } } MCMF::run(s,t); cout<<MCMF::mincost<<endl; MCMF::init(); for(int i=1;i<=m;i++){ MCMF::addEdge(s,i,numi[i],0); } for(int i=1;i<=n;i++){ MCMF::addEdge(m+i,t,numj[i],0); } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ //cout<<c<<endl; MCMF::addEdge(i,j+m,inf,-c[i][j]); } } MCMF::run(s,t); cout<<-MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
18.分配问题
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init(){ memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq)); memset(cur,0,sizeof(cur));maxflow=0; mincost=0; cnt=1; } } // namespace MCMF ll numi[105]; ll numj[105]; ll c[105][105]; void solve(){ int inf=0x3f3f3f3f3f3f; ll n; cin>>n; int s=0; int t=1000; for(int i=1;i<=n;i++){ MCMF::addEdge(s,i,1,0); MCMF::addEdge(i+n,t,1,0); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>c[i][j]; MCMF::addEdge(i,j+n,1,c[i][j]); } } MCMF::run(s,t); cout<<MCMF::mincost<<endl; MCMF::init(); for(int i=1;i<=n;i++){ MCMF::addEdge(s,i,1,0); MCMF::addEdge(i+n,t,1,0); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ MCMF::addEdge(i,j+n,1,-c[i][j]); } } MCMF::run(s,t); cout<<-MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
19.负载平衡问题
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init(){ memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq)); memset(cur,0,sizeof(cur));maxflow=0; mincost=0; cnt=1; } } // namespace MCMF ll a[105]; void solve(){ int inf=0x3f3f3f3f3f3f; ll n; cin>>n; int s=0; int t=1000; ll sum=0; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } sum/=n; for(int i=1;i<=n;i++){ MCMF::addEdge(s,i,a[i],0); MCMF::addEdge(i,t,sum,0); } for(int i=1;i<=n;i++){ int k=i+1; int j=i-1; if(j==0)j=n; if(k>n)k=1; MCMF::addEdge(i,j,inf,1); MCMF::addEdge(i,k,inf,1); } MCMF::run(s,t); cout<<MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
20.深海机器人
#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init(){ memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(inq,0,sizeof(inq)); memset(cur,0,sizeof(cur));maxflow=0; mincost=0; cnt=1; } } // namespace MCMF //ll a[105]; ll get(int i,int j){ return i*100+j+1; } ll dong[35][35]; ll bei[35][35]; void solve(){ int inf=0x3f3f3f3f3f3f; ll a,b; int s=0; int t=5000; cin>>a>>b; ll p,q; cin>>p>>q; for(int i=0;i<=p;i++){ for(int j=0;j<q;j++){ cin>>dong[i][j]; } } for(int i=0;i<=q;i++){ for(int j=0;j<p;j++){ cin>>bei[j][i]; } } for(int i=p;i>=0;i--){ for(int j=0;j<=q;j++){ if(i+1<=p) MCMF::addEdge(get(i,j),get(i+1,j),1,-bei[i][j]); if(j+1<=q){ MCMF::addEdge(get(i,j),get(i,j+1),1,-dong[i][j]); } } } for(int i=0;i<=p;i++){ for(int j=0;j<=q;j++){ if(i+1<=p) MCMF::addEdge(get(i,j),get(i+1,j),inf,0); if(j+1<=q){ MCMF::addEdge(get(i,j),get(i,j+1),inf,0); } } } for(int i=1;i<=a;i++){ ll k,x,y; cin>>k>>x>>y; MCMF::addEdge(s,get(x,y),k,0); } for(int i=1;i<=b;i++){ ll k,x,y; cin>>k>>x>>y; MCMF::addEdge(get(x,y),t,k,0); } MCMF::run(s,t); cout<<-MCMF::mincost<<endl; } int main(){ int tt=1; while(tt--){ solve(); } }
21.最长 k 可重区间集
#include <bits/stdc++.h> using namespace std; typedef long long ll; namespace MCMF { const int MAXN = 10000, MAXM = 10000, INF = 0x7fffffff; int head[MAXN], cnt = 1; struct Edge { int to, w, c, next; } edges[30000000]; inline void add(int from, int to, int w, int c) { edges[++cnt] = {to, w, c, head[from]}; head[from] = cnt; } inline void addEdge(int from, int to, int w, int c) { add(from, to, w, c); add(to, from, 0, -c); } int s, t, dis[MAXN], cur[MAXN]; bool inq[MAXN], vis[MAXN]; queue<int> Q; bool SPFA() { while (!Q.empty()) Q.pop(); copy(head, head + MAXN, cur); fill(dis, dis + MAXN, INF); dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int e = head[p]; e != 0; e = edges[e].next) { int to = edges[e].to, vol = edges[e].w; if (vol > 0 && dis[to] > dis[p] + edges[e].c) { dis[to] = dis[p] + edges[e].c; if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return dis[t] != INF; } int dfs(int p = s, int flow = INF) { if (p == t) return flow; vis[p] = 1; int rmn = flow; for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) { cur[p] = eg; int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c) { int c = dfs(to, min(vol, rmn)); rmn -= c; edges[eg].w -= c; edges[eg ^ 1].w += c; } } vis[p] = 0; return flow - rmn; } int maxflow, mincost; inline void run(int s, int t) { MCMF::s = s, MCMF::t = t; while (SPFA()) { //cout<<mincost<<endl; int flow = dfs(); maxflow += flow; mincost += dis[t] * flow; } } void init() { memset(head, 0, sizeof(head)); memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(inq, 0, sizeof(inq)); memset(cur, 0, sizeof(cur)); maxflow = 0; mincost = 0; cnt = 1; } } // namespace MCMF struct st { ll l, r; } ss[505]; bool cmp(const st &x, const st &y) { return x.l < y.l; } void solve() { int inf = 0x3f3f3f3f3f3f; int s = 0; int t = 5000; int sss = 5001; ll n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> ss[i].l >> ss[i].r; if (ss[i].l >= ss[i].r) swap(ss[i].l, ss[i].r); } sort(ss + 1, ss + 1 + n, cmp); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (ss[j].l >= ss[i].r) { MCMF::addEdge(i + 1000, j, 1, 0); } } } for (int i = 1; i <= n; i++) { MCMF::addEdge(i, i + 1000, 1, -ss[i].r + ss[i].l); MCMF::addEdge(sss, i, 1, 0); MCMF::addEdge(i + 1000, t, 1, 0); } MCMF::addEdge(s, sss, k, 0); MCMF::run(s, t); cout << -MCMF::mincost << endl; } int main() { int tt = 1; while (tt--) { solve(); } }