做网站要多,网站开发公司取名,威海网站建设公司哪家好,蜜桃传媒【网络流24题】餐巾计划问题#xff08;最小费用最大流#xff09; 题面 COGS 洛谷上的数据范围更大#xff0c;而且要开longlong 题解 餐巾的来源分为两种#xff1a; ①新买的 ②旧的拿去洗 所以#xff0c;两种情况分别建图 先考虑第一种 因为新买餐巾没有任何限制最小费用最大流 题面 COGS 洛谷上的数据范围更大而且要开longlong 题解 餐巾的来源分为两种 ①新买的 ②旧的拿去洗 所以两种情况分别建图 先考虑第一种 因为新买餐巾没有任何限制并且随时可以买 所以直接从源点向每一天连边容量为INF费用为餐巾的价格 因为流要流出去所以每个点向汇点连边容量为每天的用量费用为0 第二种旧的拿去洗 首先考虑一下怎么算有多少旧的餐巾 每天用旧的餐巾的数量值一定的不可能变多 因此从源点向这些点连边容量为每天的用量费用为0 因为旧餐巾可以累积所以从上一天向下一天连边容量为INF费用为0 接下来是快洗和慢洗这两种情况是一样的 直接从表示旧餐巾数量的这些点向洗完的那一天连边 容量为INF费用为洗餐巾的费用 这样子连边保证最大流为总的餐巾需求数 也就是说每天一定会流满因为中间的边容量是INF如果要割开只能割源点或者汇点连出去的边而这些边的容量和就是餐巾的总需求数 #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includecmath
#includealgorithm
#includeset
#includemap
#includevector
#includequeue
using namespace std;
#define INF 1000000000
#define MAXL 500000
#define MAX 2000
inline int read()
{int x0,t1;char chgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)t-1,chgetchar();while(ch9ch0)xx*10ch-48,chgetchar();return x*t;
}
int n,a[MAX];
struct Line
{int v,next,w,fy;
}e[MAXL];
int h[MAX],cnt2;
inline void Add(int u,int v,int w,int fy)
{e[cnt](Line){v,h[u],w,fy};h[u]cnt;e[cnt](Line){u,h[v],0,-fy};h[v]cnt;
}
int dis[MAX],pe[MAX],pv[MAX];
int S,T,Cost,Flow;
bool vis[MAX];
bool SPFA()
{for(int iS;iT;i)dis[i]INF;dis[S]0;queueint Q;Q.push(S);while(!Q.empty()){int uQ.front();Q.pop();for(int ih[u];i;ie[i].next){int ve[i].v;if(e[i].wdis[v]dis[u]e[i].fy){dis[v]dis[u]e[i].fy;pe[v]i;pv[v]u;if(!vis[v])vis[v]true,Q.push(v);}}vis[u]false;}if(dis[T]INF)return false;int flINF;for(int iT;i!S;ipv[i])flmin(fl,e[pe[i]].w);for(int iT;i!S;ipv[i])e[pe[i]].w-fl,e[pe[i]^1].wfl;Flowfl;Costfl*dis[T];return true;
}
int mm,ff,p;
int main()
{freopen(napkin.in,r,stdin);freopen(napkin.out,w,stdout);nread();S0,Tnn1;for(int i1;in;i)a[i]read(),Add(S,i,a[i],0),Add(in,T,a[i],0);pread();for(int i1;in;i)Add(S,in,INF,p);mmread();ffread();for(int i1;immn;i)Add(i,inmm,INF,ff);mmread();ffread();for(int i1;immn;i)Add(i,inmm,INF,ff);for(int i1;in;i)Add(i,i1,INF,0);while(SPFA());printf(%d\n,Cost);return 0;
}转载于:https://www.cnblogs.com/cjyyb/p/8175687.html
