Problem String problem （HDU5772）
题目大意
给定一个由数字组成的字符串（n<=100）,挑选出一些字符组成一个新的字符串。
字符串的价值: sigma w[id(i)][id(j))] (i !=j) id(i)为某字符在原串中的位置，w[][]为给定矩阵。
字符串的代价: 设x为数字i出现的次数，则代价为a[i]*(x-1)+b[i] (x>0) 0 (x=0)
要求最大化价值-代价。
题目分析
比较难想到的最大权闭合图模型。
昨天刚补完一道，今天又没想出来~~
搬运官方题解：
参考程序
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; #define INF 2000000000
#define V 6000
#define E 100000
int n,m,ans,dis[V],S,T; struct line{
int u,v,c,nt;
}eg[E];
int lt[V],sum=; void adt(int u,int v,int c){
eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; eg[sum].nt=lt[u]; lt[u]=sum;
} void add(int u,int v,int c){
// printf("%d %d %d\n",u,v,c );
adt(u,v,c); adt(v,u,);
} void init(){
memset(lt,,sizeof(lt));
sum=; ans=;
} bool bfs(){
memset(dis,,sizeof(dis));
dis[S]=;
queue<int> Q;
Q.push(S);
while (!Q.empty()){
int u=Q.front();
Q.pop();
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (eg[i].c && !dis[v]){
dis[v]=dis[u]+;
Q.push(v);
}
}
}
return dis[T]>;
} int dfs(int u,int flow){
if (u==T) return flow;
int res=,f;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (eg[i].c&&dis[v]==dis[u]+){
f=dfs(v,min(flow-res,eg[i].c));
res+=f;
eg[i].c-=f;
eg[i ^ ].c+=f;
if (flow==res) break;
}
}
if (!res) dis[u]=-;
return res;
} int dinic(){
int sum=;
while (bfs()) sum+=dfs(S,INF);
return sum;
} int main(){ int Tp,cas=,cnt;
char s[];
int a[],b[],w[][]; scanf("%d",&Tp);
while (Tp--){
init(); scanf("%d",&n);
scanf("%s",s+);
for (int i=;i<=;i++) scanf("%d%d",&a[i],&b[i]);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
scanf("%d",&w[i][j]);
ans+=w[i][j];
}
S=,T=n*(n-)/+n++,cnt=;
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++){
cnt++;
add(S,cnt,w[i][j]+w[j][i]);
add(cnt,n*(n-)/+i,INF);
add(cnt,n*(n-)/+j,INF);
}
for (int i=;i<=n;i++){
add(n*(n-)/+i,n*(n-)/+n+s[i]-''+,INF);
add(n*(n-)/+i,T,a[s[i]-'']);
}
for (int i=;i<=;i++)
add(n*(n-)/+n+i+,T,(b[i]-a[i]));
n=T;
printf("Case #%d: %d\n",++cas,ans-dinic());
}
}