网络流的应用太多了, 对于各种网络流的题目, 要熟练运用建模思想, 将实际问题转化为网络流模型.
GO: 洛谷
我们将问题划分成几个子问题:
1."餐巾的数量","需要的费用","天数" 分别指代什么?
2. 快洗, 慢洗会对哪些状态造成影响?
3. 如何建立 (记录) 影响与影响间的关系
......
首先, 分析题意, 不难发现这是一道最小费用最大流的问题. 我们按贪心的思想看, 每天分配好所需要的餐巾是基本任务, 而让所花的费用最小是优化方案.
因此, 分配餐巾对应着网络中的流, 而费用就是费用.
快洗, 慢洗等状态会为未来的某一天增加餐巾, 因此影响的对象是未来洗完的那一天.
我们将一天分为两个状态: 消耗餐巾和送出餐巾.
消耗餐巾, 在网络流中即为消耗流(使用餐巾), 而送出对应着增加花费(洗餐巾), 这样就将模型初步建立完成了.
而对于程序本身而言, 一个流为 inf 的边, 代表可以随便走, 最终这条边也不会被删去, 但是只要走过了就会消耗费用, 比如将今天的餐巾送出去洗. 而一个流为 0, 费用为 0 的边, 可以当做一个状态的转移, 比如将今天的餐巾堆积到明天, 既不消耗费用也不使用餐巾. 所以限制好一些条件, 让程序自己完成任务即可, 这是网络流最大的魅力所在.
- #include<bits/stdc++.h>
- #define f(i,a,b) for(int i=a;i<=b;i++)
- using namespace std;
- typedef long long ll;
- const int inf=1e9;
- const int N=2e5+10;
- int n,s,t,vf,tf,vs,ts,co,cnt=-1,sum;
- int head[N],vis[N],l[N],pre[N],flow[N],dis[N];
- struct edge{int to,next,f,w;}e[N];
- void addedge(int from,int to,int f,int w){
- e[++cnt]=(edge){to,head[from],f,w}; head[from]=cnt;
- }
- queue<int> q;
- bool spfa(){
- memset(vis,0,sizeof(vis));
- memset(dis,0x7f,sizeof(dis));
- dis[s]=pre[t]=0;
- q.push(s);
- flow[s]=inf;
- vis[s]=1;
- while(!q.empty()){
- int u=q.front();
- vis[u]=0;
- for(int i=head[u];i!=-1;i=e[i].next){
- int v=e[i].to,f=e[i].f,w=e[i].w;
- if(f>0&&dis[v]>dis[u]+w){
- dis[v]=dis[u]+w;
- pre[v]=u;
- l[v]=i;
- flow[v]=min(flow[u],f);
- if(!vis[v]){
- q.push(v);
- vis[v]=1;
- }
- }
- }
- q.pop();
- }
- return pre[t];
- }
- void solve(){
- ll ansc=0;
- while(spfa()){
- ansc+=flow[t]*dis[t];
- for(int i=t;i!=s;i=pre[i]){
- int ed=l[i];
- e[ed].f-=flow[t];
- e[ed^1].f+=flow[t];
- }
- }
- printf("%lld",ansc);
- }
- int main(){
- // freopen("dat.in","r",stdin);
- memset(head,-1,sizeof(head));
- scanf("%d",&n);
- t=n<<1|1;s=0;
- f(i,1,n){
- scanf("%d",&sum);
- addedge(s,i,sum,0);
- addedge(i,s,0,0);
- addedge(i+n,t,sum,0);
- addedge(t,i+n,0,0);
- }
- scanf("%d%d%d%d%d",&co,&tf,&vf,&ts,&vs);
- f(i,1,n){
- if(i+1<=n) addedge(i,i+1,inf,0),addedge(i+1,i,0,0);
- if(i+tf<=n) addedge(i,i+n+tf,inf,vf),addedge(i+n+tf,i,0,-vf);
- if(i+ts<=n) addedge(i,i+n+ts,inf,vs),addedge(i+n+ts,i,0,-vs);
- addedge(s,i+n,inf,co);
- addedge(i+n,s,0,-co);
- }
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3152725.html