题面题解这是一道很裸很裸的最大权值闭合子图。然而被暴力蒙蔽了双眼的我真的没看出来，我还是太菜了！一看cost的定义，以及分段的方式，非常符合网络流的特性。构图：对于wi,
题面
题解
这是一道很裸很裸的最大权值闭合子图。然而被暴力蒙蔽了双眼的我真的没看出来，我还是太菜了！ 一看cost的定义，以及分段的方式，非常符合网络流的特性。 构图：
- 对于 wi,j + wj,i 建一个点，
- 对于每个位置建一个点，代价为 −a
- 对于每个字符建一个点，代价为 −b + a
- 一类点连向二类点，二类点连向三类点
代码#include#include#includeusing namespace std;#define MAXN 450000#define MAXM 120int End[MAXN],Next[MAXN],Last[MAXN],Len[MAXN],e=1;void add(int x,int y,int L){ Len[++e]=L; End[e]=y; Next[e]=Last[x]; Last[x]=e; return ;}void _r(int while(c'9') { c=getchar(); } for(x=0;c>='0'c=getchar()) { x=(x<<1)+(x<<3)+c-'0'; } return ;}int A[MAXM],B[MAXM],w[MAXM][MAXM],tot,S,E,n;char s[MAXM];int dis[MAXN],cnt[MAXN],id[MAXM][MAXM],pp[MAXM],qq[20];const int inf=0x3c3c3c3c;int dfs(int u,int flow){ int delta=0,tmp,v; if(u==E) { return flow; } for(int t=Last[u];t;t=Next[t]) { v=End[t]; if(Len[t]>0 delta+=tmp; Len[t]-=tmp; Len[t^1]+=tmp; if(delta==flow||dis[S]>=tot) { return delta; } } } if(dis[S]>=tot) { return delta; } cnt[dis[u]]--; if(cnt[dis[u]]==0) { dis[S]=tot; } cnt[++dis[u]]++; return delta;}void work(){ memset(dis,0,sizeof(dis)); memset(cnt,0,sizeof(cnt)); e=1; memset(Last,0,sizeof(Last)); _r(n); tot=0; scanf("%s",s+1); for(int i=0;i<10;i++) { _r(A[i]); _r(B[i]); } S=++tot; E=++tot; int ans=0; for(int i=0;i<10;i++) { qq[i]=++tot; add(tot,E,B[i]-A[i]); add(E,tot,0); } for(int i=1;i<=n;i++) { pp[i]=++tot; add(tot,E,A[s[i]-'0']); add(E,tot,0); add(tot,qq[s[i]-'0'],inf); add(qq[s[i]-'0'],tot,0); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { _r(w[i][j]); if(i!=j) { ans+=w[i][j]; } } } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { id[i][j]=++tot; add(S,tot,w[i][j]+w[j][i]); add(tot,S,0); add(tot,pp[i],inf); add(pp[i],tot,0); add(tot,pp[j],inf); add(pp[j],tot,0); } } while(dis[S]
上一篇：句柄“94bc”,多重从属对象,句柄7
下一篇：没有了
上一篇：句柄“94bc”,多重从属对象,句柄7
下一篇：没有了