解析：
多校标答
第一类：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+7; const int maxn=102; const int maxnode=maxn*maxn; int N,a[10],b[10],w[maxn][maxn]; int eid,S,T; //eid用于边的编号，S,T分别为源点汇点 vector<int> G[maxnode]; //存储边的编号 struct edge { int u,v,cap,flow; //头，尾，容量和流量 edge(int u=0,int v=0,int cap=0,int flow=0):u(u),v(v),cap(cap),flow(flow){} }E[maxnode*10]; void AddEdge(int u,int v,int c) //建边 { E[eid]=edge(u,v,c,0); //正向边 G[u].push_back(eid); eid++; E[eid]=edge(v,u,0,0); //反向边 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]=0; que.push(S); while(!que.empty()) { int u=que.front(); que.pop(); int Size=G[u].size(); for(int i=0;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]+1; que.push(v); } } } return vis[T]; } int DFS(int u,int a) //分层 { if(u==T||a==0) return a; int ret=0,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]+1==d[v]&&(f=DFS(v,min(a,e.cap-e.flow)))>0) { ret+=f; e.flow+=f; E[id^1].flow-=f; a-=f; if(a==0) break; } } return ret; } int MaxFlow(int s,int t) //最大流Dinic算法 { S=s; T=t; int ret=0; while(BFS()) { memset(cur,false,sizeof(cur)); ret+=DFS(S,INF); } return ret; } int main() { int TT,Case=0; scanf("%d",&TT); while(TT--) { char SS[maxn]; scanf("%d",&N); scanf("%s",SS); for(int i=0;i<10;i++) scanf("%d%d",&a[i],&b[i]); int be=N*N+N+10; int en=be+1; for(int i=0;i<=en;i++) G[i].clear(); eid=0; int ans=0; for(int i=0;i<N;i++) for(int j=0;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=0;i<N;i++) AddEdge(N*N+i,N*N+N+SS[i]-'0',INF); for(int i=0;i<N;i++) AddEdge(N*N+i,en,a[SS[i]-'0']); for(int i=0;i<10;i++) AddEdge(N*N+N+i,en,b[i]-a[i]); printf("Case #%d: %d ",++Case,ans-MaxFlow(be,en)); } return 0; }