求助费用流

#define int long long
const int MAXM=12,MAXN=1e4+10,MAXK=1e4+10,MAXV=1e4+10,MAXE=1e6+10;
const int INF=0x3f3f3f3f;
int M,N,K,S,T;
int Wgt[MAXN];
struct Net
{
	int next,to,val,cost;
	Net(int n=0,int t=0,int v=0,int c=0):next(n),to(t),val(v),cost(c){}
}Edge[MAXE<<1];
int Head[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w,int c)
{
    Edge[++Total]=Net(Head[u],v,w,c);Head[u]=Total;
    Edge[++Total]=Net(Head[v],u,0,-c);Head[v]=Total;
}
int Dist[MAXV],ret;
bool Vis[MAXV];
inline bool Spfa(int s,int t)
{
	for(int i=1;i<=K;++i) Dist[i]=INF;
	for(int i=1;i<=K;++i) Cur[i]=Head[i];
    std::queue<int>Q;
    Q.push(s),Dist[s]=0,Vis[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        Vis[u]=0;
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Edge[e].val&&Dist[v]>Dist[u]+Edge[e].cost)
            {
                Dist[v]=Dist[u]+Edge[e].cost;
            	if(!Vis[v]) Q.push(v),Vis[v]=1;
            }
        }
    }
    return Dist[t]!=INF;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    Vis[x]=1;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e,v=Edge[e].to;
        if(!Vis[v]&&Edge[e].val&&Dist[v]==Dist[x]+Edge[e].cost)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(k)
            {
                ret+=k*Edge[e].cost;
                Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
            }
        }
    }
    Vis[x]=0;
    return flow;
}
inline int SSP()
{
    int res=0,flow;
    while(Spfa(S,T)) while(flow=Dfs(S,INF)) res+=flow;
    return res;
}
int Sum,Lst[MAXN];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(M,N,K);S=1,T=K;
	for(int i=1;i<=N;++i) read(Wgt[i]);
	std::memset(Lst,-1,sizeof(Lst));
	for(int i=1,x;i<=K;++i)
	{
		read(x);Sum+=Wgt[x];
		addEdge(Lst[x]+1,i,1,-Wgt[x]);
		Lst[x]=i;
	}
	addEdge(1,2,M-1,0);
	for(int i=2;i<K;++i) addEdge(i,i+1,INF,0);
	SSP();
	write(Sum+ret);
	return 0;
}
/*

*/