最小费用流。
CODE:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cassert>
using namespace std;
#define oo 0x7f7f7f7f
#define MAXEDGE 510000
#define MAXV 1002
typedef struct struct_edge* edge;
struct struct_edge{int v,c,d;edge n,b;};
struct_edge pool[MAXEDGE];
edge top;
int S,T,V;
edge adj[MAXV];
int q[MAXV];
bool inq[MAXV];
int head,tail;
edge p[MAXV];
int d[MAXV];
void add_edge(int u,int v,int c,int d)
{
top->v=v,top->c=c,top->d=d,top->n=adj[u],adj[u]=top++;
top->v=u,top->c=0,top->d=-d,top->n=adj[v],adj[v]=top++;
adj[u]->b=adj[v];
adj[v]->b=adj[u];
}
int min_cost_flow(int n,int t)
{
int flow=0,cost=0;
for (;;)
{
memset(d,oo,sizeof(d));
inq[q[head=tail=0]=S]=true;
d[S]=0;
p[S]=0;
while (head<=tail)
{
int u;
inq[u=q[(head++)%MAXV]]=false;
for (edge i=adj[u];i;i=i->n)
if (i->c&&d[i->v]>d[u]+i->d)
{
if (!inq[i->v])
inq[q[(++tail)%MAXV]=i->v]=true;
d[i->v]=d[u]+i->d;
p[i->v]=i;
}
}
if (d[T]==oo) break;
else
{
int delta=oo;
for (edge i=p[T];i;i=p[i->b->v])
if (delta>i->c) delta=i->c;
for (edge i=p[T];i;i=p[i->b->v])
i->c-=delta,i->b->c+=delta;
flow+=delta;
cost+=d[T]*delta;
}
}
if (flow!=n) return 1+t;
return cost;
}
int E;
int u[MAXEDGE],v[MAXEDGE];
int n;
int mine[MAXV];
int price[MAXV];
bool source[MAXV];
int total_price;
int result(int t)
{
if (t)
{
int answer=-1,i=0;
if (t==n)
{
source[0]=true;
int get=result(t-1);
if (get>answer) answer=get;
source[0]=false;
}
else
{
int k=n-t;
while (k) if (source[i++]) k–;
while (i<n*2)
{
if (!source[i])
{
source[i]=true;
int get=result(t-1);
if (get>answer) answer=get;
source[i]=false;
}
i++;
}
}
return answer;
}
else
{
memset(adj,0,sizeof(adj));
top=pool;
S=V+V,T=V+V+1;
for (int i=0;i<E;i++)
add_edge(u[i]+V,v[i],1,0),
add_edge(v[i]+V,u[i],1,0);
for (int i=0;i<V;i++)
add_edge(i,i+V,1,price[i]);
for (int i=0;i<n*2;i++)
if (source[i]) add_edge(S,mine[i],1,0);
else add_edge(mine[i]+V,T,1,0);
return total_price-min_cost_flow(n,total_price);
}
}
int main()
{
int T;
cin>>T;
for (int t=0;t<T;t++)
{
cin>>V>>E;
for (int i=0;i<E;i++)
cin>>u[i]>>v[i];
cin>>n;
for (int i=0;i<n*2;i++) cin>>mine[i];
total_price=0;
for (int i=0;i<V;i++) cin>>price[i],total_price+=price[i];
cout<<result(n)<<endl;
}
}