最大权闭合子图。建图巧妙。
最大权闭合子图：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn = 30000 + 10; const int INF = 0x7FFFFFFF; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {} }; vector<Edge>edges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int n, m, s, t; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int w = edges.size(); G[from].push_back(w - 2); G[to].push_back(w - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (d[x]+1 == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow; } int dinic(int s, int t) { int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } const int MAXM=110; int T,len,a[MAXM],b[MAXM],w[MAXM][MAXM],val[2*MAXM*MAXM],ans; char str[MAXM]; int main() { scanf("%d",&T); int cas=1; while(T--) { scanf("%d",&len); scanf("%s",str); for(int i=0;i<10;i++) scanf("%d%d",&a[i],&b[i]); for(int i=0;i<len;i++) for(int j=0;j<len;j++) scanf("%d",&w[i][j]); init(); ans=0; s=len*len+len+10; val[s]=0; t=len*len+len+10+1; val[t]=0; for(int i=0;i<len;i++) for(int j=i+1;j<len;j++) { val[i*len+j]=w[i][j]+w[j][i]; AddEdge(i*len+j,len*len+i,INF); AddEdge(i*len+j,len*len+j,INF); if(val[i*len+j]>0) AddEdge(s,i*len+j,val[i*len+j]), ans=ans+val[i*len+j]; else if(val[i*len+j]<0) AddEdge(i*len+j,t,-val[i*len+j]); } for(int i=len*len;i<=len*len+len-1;i++) { val[i]=-a[str[i-len*len]-'0']; AddEdge(i,len*len+len+str[i-len*len]-'0',INF); if(val[i]>0) AddEdge(s,i,val[i]), ans=ans+val[i]; else if(val[i]<0) AddEdge(i,t,-val[i]); } for(int i=len*len+len;i<=len*len+len+10-1;i++) { val[i]=-b[i-(len*len+len)]+a[i-(len*len+len)]; if(val[i]>0) AddEdge(s,i,val[i]), ans=ans+val[i]; else if(val[i]<0) AddEdge(i,t,-val[i]); } ans=ans-dinic(s,t); printf("Case #%d: %d ",cas++,ans); } return 0; }