运输问题
建模之后就是费用流板题. 建模方法就是两边一排.
注意重置边的时候, 不能 swap, 要用 \(+=\) 原因思考一下显然, 不然就会不知道哪里错了.
强行总结的话, 这样的建模体现了一个且的关系.
- //@winlere
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- using namespace std; typedef long long ll;
- inline int qr(){
- register int ret=0,f=0;
- register char c=getchar();
- while(c<48||c>57)f|=c==45,c=getchar();
- while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
- return f?-ret:ret;
- }
- const int maxn=25050;
- int n,m,S,T,nodecnt;
- const int inf=0x3f3f3f3f;
- struct E{
- int to,nx,c,w;
- }e[maxn<<2|1];
- int head[maxn];
- int cnt=-1;
- inline void add(const int&fr,const int&to,const int&w,const int&c,const bool&f){
- //printf("fr=%d to=%d w=%d c=%d\n",fr,to,w,c);
- e[++cnt]={to,head[fr],c,w};
- head[fr]=cnt;
- if(f)add(to,fr,0,-c,0);
- }
- inline int mincost(){
- int cost=0,fl=0;
- int d[maxn],last[maxn],flow[maxn],in[maxn];
- queue <int> q;
- while(1){
- while(!q.empty())q.pop();
- for(register int t=0;t<=m+n+2;++t) d[t]=inf,flow[t]=0,last[t]=0,in[t]=0;
- d[S]=0;flow[S]=inf;
- q.push(S);
- while(!q.empty()){
- register int now=q.front();
- in[now]=0;
- q.pop();
- //cout<<"now="<<now<<endl;
- for(register int t=head[now];t!=-1;t=e[t].nx){
- if(e[t].w>0&&d[e[t].to]>d[now]+e[t].c){
- //cout<<e[t].to<<endl;
- d[e[t].to]=d[now]+e[t].c;
- flow[e[t].to]=min(flow[now],e[t].w);
- last[e[t].to]=t;
- if(!in[e[t].to])q.push(e[t].to);
- in[e[t].to]=1;
- }
- }
- }
- if(!flow[T]) break;
- fl+=flow[T];
- cost+=flow[T]*d[T];
- for(register int t=T;t!=S;t=e[last[t]^1].to)
- e[last[t]].w-=flow[T],e[last[t]^1].w+=flow[T];
- }
- return cost;
- }
- inline int maxcost(){
- queue <int> q;
- int cost=0,fl=0;
- int d[maxn],last[maxn],flow[maxn],in[maxn];
- while(1){
- while(!q.empty())q.pop();
- for(register int t=0;t<=m+n+20;++t) d[t]=-inf,flow[t]=0,last[t]=0,in[t]=0;
- d[S]=0;flow[S]=inf;
- q.push(S);
- while(!q.empty()){
- register int now=q.front();
- in[now]=0;
- q.pop();
- //cout<<"now="<<now<<endl;
- for(register int t=head[now];t!=-1;t=e[t].nx){
- if(e[t].w&&d[e[t].to]<d[now]+e[t].c){
- d[e[t].to]=d[now]+e[t].c;
- //cout<<e[t].to<<' '<<d[e[t].to]<<endl;
- flow[e[t].to]=min(flow[now],e[t].w);
- last[e[t].to]=t;
- if(!in[e[t].to])q.push(e[t].to);
- in[e[t].to]=1;
- }
- }
- }
- if(!flow[T]) break;
- fl+=flow[T];
- cost+=flow[T]*d[T];
- for(register int t=T;t!=S;t=e[last[t]^1].to)
- e[last[t]].w-=flow[T],e[last[t]^1].w+=flow[T];
- }
- return cost;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in.in","r",stdin);
- //freopen("out.out","w",stdout);
- #endif
- memset(head,-1,sizeof head);
- m=qr();n=qr();
- S=++nodecnt; T=m+n+2;
- for(register int t=1;t<=m;++t)
- add(S,t+1,qr(),0,1);
- for(register int t=1;t<=n;++t)
- add(t+m+1,T,qr(),0,1);
- for(register int t=1;t<=m;++t)
- for(register int i=1;i<=n;++i)
- add(1+t,1+m+i,inf,qr(),1);
- printf("%d\n",mincost());
- for(register int t=0;t<=cnt;++t)
- if(t>(t^1)){
- e[t^1].w+=e[t].w;
- e[t].w=0;
- }
- printf("%d\n",maxcost());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3132561.html