解析：
多校标答
第一类：Pij 表示第i个点和第j个点组合的点，那么Pij的权值等于w[i][j]+w[j][i]（表示得分）
第二类：原串中的n个点每个点拆出一个点，第i个点权值为 –a[s[i]] （表示要花费）
第三类：对于10种字符拆出10个点，每个点的权值为 -(b[x]-a[x])
最大权闭合图用网络流求解，根据原图建立一个等价的网络，构建规则如下。
对于点权为正的节点，从源点连一条容量为点权的边到该点，对于点权为负的边，从该点连一条容量为点权绝对值的边到汇点。原图中的边保留，容量为inf。最大权值即为图中所有正点权之和减去最大流。
这题我看了半天才理解。。。。。
代码
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=1e9+;
const int maxn=;
const int maxnode=maxn*maxn;
int N,a[],b[],w[maxn][maxn];
int eid,S,T; //eid用于边的编号，S,T分别为源点汇点
vector<int> G[maxnode]; //存储边的编号
struct edge
{
int u,v,cap,flow; //头，尾，容量和流量
edge(int u=,int v=,int cap=,int flow=):u(u),v(v),cap(cap),flow(flow){}
}E[maxnode*];
void AddEdge(int u,int v,int c) //建边
{
E[eid]=edge(u,v,c,); //正向边
G[u].push_back(eid); eid++;
E[eid]=edge(v,u,,); //反向边
G[v].push_back(eid); eid++;
}
bool vis[maxnode];
int d[maxnode],cur[maxnode];
queue<int> que;
bool BFS()
{
memset(vis,false,sizeof(vis));
while(!que.empty()) que.pop();
vis[S]=true;
d[S]=;
que.push(S);
while(!que.empty())
{
int u=que.front(); que.pop();
int Size=G[u].size();
for(int i=;i<Size;i++)
{
int id=G[u][i];
edge& e=E[id];
int v=e.v;
if(!vis[v]&&e.cap>e.flow)
{
vis[v]=true;
d[v]=d[u]+;
que.push(v);
}
}
}
return vis[T];
}
int DFS(int u,int a) //分层
{
if(u==T||a==) return a;
int ret=,f;
int Size=G[u].size();
for(int& i=cur[u];i<Size;i++)
{
int id=G[u][i];
edge& e=E[id];
int v=e.v;
if(d[u]+==d[v]&&(f=DFS(v,min(a,e.cap-e.flow)))>)
{
ret+=f;
e.flow+=f;
E[id^].flow-=f;
a-=f;
if(a==) break;
}
}
return ret;
}
int MaxFlow(int s,int t) //最大流Dinic算法
{
S=s; T=t;
int ret=;
while(BFS())
{
memset(cur,false,sizeof(cur));
ret+=DFS(S,INF);
}
return ret;
}
int main()
{
int TT,Case=;
scanf("%d",&TT);
while(TT--)
{
char SS[maxn];
scanf("%d",&N);
scanf("%s",SS);
for(int i=;i<;i++) scanf("%d%d",&a[i],&b[i]);
int be=N*N+N+;
int en=be+;
for(int i=;i<=en;i++) G[i].clear(); eid=;
int ans=;
for(int i=;i<N;i++)
for(int j=;j<N;j++)
{
scanf("%d",&w[i][j]);
if(i==j) continue;
ans+=w[i][j];
AddEdge(be,i*N+j,w[i][j]);
AddEdge(i*N+j,N*N+i,INF);
AddEdge(i*N+j,N*N+j,INF);
}
for(int i=;i<N;i++) AddEdge(N*N+i,N*N+N+SS[i]-'',INF);
for(int i=;i<N;i++) AddEdge(N*N+i,en,a[SS[i]-'']);
for(int i=;i<;i++) AddEdge(N*N+N+i,en,b[i]-a[i]);
printf("Case #%d: %d\n",++Case,ans-MaxFlow(be,en));
}
return ;
}