7 条题解
-
2
这道题……可以用網絡流来解决欸!
首先考虑可行性。
首先建立一个超源和超汇,记为s与t; 然后在两点间建边,构成一个穿新的网络~ 最后重要的来了,很显然,从超源到超汇即s到t的最大流记为flow就是所谓的“和”——这道题的答案! 自此,证明完成,可以开始写代码了。
要代码的看这里!!!
接下来就是非常简单的网络流板子,顺便贴个标签,以供大家更快地“学会”网络流❤️❤️❤️
#include <bits/stdc++.h> #define inf 2005020600 using namespace std; int n,m,fir[2001],num=1,a,b; long long ans=0,level[2001],now[2001]; struct g{ int nxt,to; long long p; }flow[2001]; void add(int s,int e,long long c){ flow[++num].to=e; flow[num].nxt=fir[s]; flow[num].p=c; fir[s]=num; flow[++num].to=s; flow[num].nxt=fir[e]; flow[num].p=0; fir[e]=num; } bool bfs() { for (int i=1;i<=m;i++){ level[i]=inf; } queue <int> q; q.push(1); level[1]=0; now[1]=fir[1]; while (!q.empty()){ int pre=q.front(); q.pop(); for (int i=fir[pre];i;i=flow[i].nxt){ int go=flow[i].to; if (level[go]==inf && flow[i].p>0){ now[go]=fir[go]; q.push(go); level[go]=level[pre]+1; if (go==m){ return 1; } } } } return 0; } int dfs(int pos,int f) { if (pos==m){ return f; } int a,res=0; for (int i=now[pos];i&&f;i=flow[i].nxt) { int go=flow[i].to; now[pos]=i; if (level[go]==level[pos]+1 && flow[i].p>0){ a=dfs(go,fmin(flow[i].p,f)); if (a==0){ level[go]=inf; } f-=a; res+=a; flow[i].p-=a; flow[i^1].p+=a; } } return res; } int main() { n=2,m=2; cin>>a>>b; add(1,2,a); add(1,2,b); while (bfs()){ ans+=dfs(1,inf); } cout<<ans; }
信息
- ID
- 1
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 563
- 已通过
- 229
- 上传者