感慨:网络流的题真是神奇啊
一开始拆点,想了几个建法,但不知出了这个问题就有了那个问题。。
于是看了看题解
1、从S向每个Xi连一条容量为ri,费用为0的有向边。
2、从每个Yi向T连一条容量为ri,费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大,费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个Xi向Yi+m+1(i+m+1<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个Xi向Yi+n+1(i+n+1<=N)连一条容量为无穷大,费用为s的有向边。
那我也讲一下我的想法。。
大概入点的意思就是说这一天有多少个盘子脏的,要洗的
然后出点就是这一天要用的盘子啦!
每一条只用ni个,不会用多
剩下的就放到后面去
然后你现在用不完的现在洗和以后洗是都可以的,于是有x连x+1
大概就是这样子了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int n,a,b,f,fa,fb;
const int N=1005*2;
const int M=500000;
const int MAX=1<<30;
struct qq
{int x,y,z,z1,last;
}s[M];int num,last[N];
int S,T;
void init (int x,int y,int z,int z1)
{num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].z1=z1;s[num].last=last[x];last[x]=num;swap(x,y);z=0;z1=-z1;num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].z1=z1;s[num].last=last[x];last[x]=num;
}
int from[N];
bool in[N];
int g[N];
bool SPFA ()
{memset(g,127,sizeof(g));memset(in,false,sizeof(in));memset(from,-1,sizeof(from));queue<int> q;q.push(S);in[S]=true;g[S]=0;while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (g[y]>g[x]+s[u].z1&&s[u].z>0){g[y]=g[x]+s[u].z1;from[y]=u;if (!in[y]){in[y]=true;q.push(y);}}}in[x]=false;}return from[T]!=-1;
}
int ans=0;
void get ()
{int x=MAX,now=from[T];while (now!=-1){x=min(x,s[now].z);now=from[s[now].x];}now=from[T];while (now!=-1){ans=ans+s[now].z1*x;s[now].z-=x;s[now^1].z+=x;now=from[s[now].x];}return ;
}
int main()
{num=1;memset(last,-1,sizeof(last));scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);S=2*n+1;T=S+1;for (int u=1;u<=n;u++){int w;scanf("%d",&w);init(S,u,w,0);init(u+n,T,w,0);if (u+a+1<=n) init(u,u+a+n+1,MAX,fa);if (u+b+1<=n) init(u,u+b+n+1,MAX,fb);if (u<n) init(u,u+1,MAX,0);init(S,u+n,MAX,f);}while (SPFA()==true) get();printf("%d\n",ans);return 0;
}