本文共 2566 字，大约阅读时间需要 8 分钟。
最大权闭合子图。建图巧妙。
最大权闭合子图：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include 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 edges;vector 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 Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i 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 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 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\n",cas++,ans); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5722351.html
