hdu 5772 String problem 最大权闭合子图
DescriptionThis is a simple problem about string. Now a string S contains only ‘0’-‘9’. ?? wants to select a subsequence from this string. And makes this subsequence score maximum. The subsequence’s score is calculated as follows:Score= Value – Total_Cost
The calculation of the Cost is as follows:
If the number of characters x in the subsequence is kx, And the two coefficients are ax,bx,The cost of character x calculated as follows:{cost=0,kx=0cost=ax∗(kx−1)+bx,kx≠0TotalCost=∑i=09costThe calculation of the Value is as follows:Value=0;
for(int i=1;i<=length(substr);++i){
for(int j=1;j<=length(substr);++j){
if(i!=j)
Value+=w]];
}
}id is the position of the subsequence’s ith character in the original string,for example,if the original string is “13579”,and the subsubquence is “159”,then the array id ={1,3,5}. The w is a weight matrix.InputThe first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains one integers n, the length of a string.
Next line contains the string S.
Next ten lines,each line contains ai,bi,denote the char i’s(0-9) coefficients
Next is a n*n matrix w.
Limits:
T<=20,
0<=n<=100
0<=ai<=bi<=1000
0<=w<=50OutputEach test output one line “Case #x: y” , where x is the case number ,staring from 1. y is the Maximum score.Sample Input1
3
135
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
0 0 3
1 0 0
4 0 0Sample OutputCase #1: 3Hint
we can choose “15”，id[]={1,3} then Value=w+w=7,
Total_Cost=2+2=4，Score=7-4=3Hint题意给你一个字符串，只含有数字。你需要选择出一个子序列，使得这个子序列的权值最大。这个子序列如果这个数字第一次出现就ans-=bx，否则就-=ax然后如果第i个字符和第j个字符都在子序列里面，那么ans+=w问你最大ans是多少题解：比较显然的就是最大闭合子图了，这个跑网络流就是了。标准题解：网络流：最大权闭合子图。
思路如下：首先将点分为3类第一类：Pij 表示第i个点和第j个点组合的点，那么Pij的权值等于w+w（表示得分）第二类：原串中的n个点每个点拆出一个点，第i个点权值为 –a] （表示要花费）第三类：对于10种字符拆出10个点，每个点的权值为 -(b-a)那么我们可以得到一个关系图 ，对于第一类中的点Pij，如果想要选择Pij，你就必须要选中第二类中的点i和j，对于第二类中的点如果你想选中第i个点，其对应的字符s，那么就必须选中第三类中s 对应的点，因为每个种类的点第一次选中时花费是b]，而第二类中花费都是a],一定要补上b]-a]，而且只需要补上一次。得到上面的关系图后然后就是普通的最大权闭合子图问题,直接求解即可。但是我们队比较邪，我们先2^10枚举了一下，然后再跑的网络流，但是这样会TLE。于是我们就XJB只搜了后面的几个状态和前面的状态，然后跑网络流就过了……下面代码是我们队的谐星做法，非正解，正解按照前面的思路建图就好了。另外这个图跑ISAP比跑dinic快的多。。。。
代码#include<bits/stdc++.h>
#define Maxn 60009
#define Maxm 400009
#define inf 100000000
#define LL int
using namespace std;
const int MAXN=100000,MAXM=100000;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E;
int G,cur,pre,dis,gap,N,sz;
void init(int _n)
{
N=_n,sz=0; memset(G,-1,sizeof(G)*N);
}
void link(int u,int v,int c)
{
E=Edge(v,c,0,G); G=sz++;
E=Edge(u,0,0,G); G=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=0,aug=inf,flag=false,u,v;
for (int i=0;i<N;++i)cur=G,gap=dis=0;
for (gap=N,u=pre=S;dis<N;flag=false)
{
for (int &it=cur;~it;it=E.nx)
{
if (E.c>E.f&&dis==dis.v]+1)
{
if (aug>E.c-E.f) aug=E.c-E.f;
pre=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E]].f+=aug;
E^1].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G;~it;it=E.nx)
{
if (E.c>E.f&&dis.v]<mx)
{
mx=dis.v]; cur=it;
}
}
if ((--gap])==0) break;
++gap=mx+1]; u=pre;
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q; memset(dis,-1,sizeof(dis)*N);
dis=0; Q=S;
for (int h=0,t=1,u,v,it;h<t;++h)
{
for (u=Q,it=G;~it;it=E.nx)
{
if (dis.v]==-1&&E.c>E.f)
{
dis=dis+1; Q=v;
}
}
}
return dis!=-1;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=0,tmp,v;
for (int &it=cur;~it&&ret<low;it=E.nx)
{
if (dis.v]==dis+1&&E.c>E.f)
{
if (tmp=dfs(v,T,min(low-ret,E.c-E.f)))
{
ret+=tmp; E.f+=tmp; E.f-=tmp;
}
}
}
if (!ret) dis=-1; return ret;
}
int dinic(int S,int T)
{
int maxflow=0,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G)*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
struct st
{
int u,v;
LL value;
}e;
int cost;
int mp;
int a,b,nn;
int Ans = 0;
string s;
LL get(int zt){
vector<int> tmp;
LL sum=0;
int cccc = 0;
for(int i=0;i<10;i++){
if((1<<i)&zt){
sum-=(b-a);
}
}
for(int i=0;i<s.size();i++){
int num = s-'0';
if((1<<num)&zt){
tmp.push_back(i+1);
cost=a-'0'];
// cout<<i<<" ";
}
}
int m = 1;
for(int i=0;i<tmp.size();i++){
for(int j=i+1;j<tmp.size();j++){
e.u=tmp;
e.v=tmp;
e.value=mp]]+mp]];
sum+=e.value;
m++;
}
}
if(sum<=Ans)return 0;
m--;
init(12000);
int n = tmp.size();
for(int i=1;i<=m;i++)
{
link(0,i,e.value);
link(i,m+e.u,inf);
link(i,m+e.v,inf);
}
for(int i=1;i<=n;i++)
link(tmp+m,m+nn+1,cost]);
LL ans=ISAP(0,m+nn+1);
return sum-ans;
}
int cas = 0;
int vvv;
int ccc = 0;
int times = 0 ;
void dfs1(int x,int tmp,int k){
if(x==10){
if( (k>=ccc-7||ccc<=2) )Ans=max(Ans,get(tmp));
return;
}
if(vvv)dfs1(x+1,tmp|(1<<x),k+1);
dfs1(x+1,tmp,k);
}
void solve(){
memset(vvv,0,sizeof(vvv));
Ans=0;
times=0;
scanf("%d",&nn);
cin>>s;
ccc=0;
for(int i=0;i<s.size();i++){
if(vvv-'0']==0)ccc++;
vvv-'0']=1;
}
for(int i=0;i<10;i++){
scanf("%d%d",&a,&b);
}
for(int i=1;i<=nn;i++){
for(int j=1;j<=nn;j++){
scanf("%d",&mp);
}
}
dfs1(0,0,0);
cout<<"Case #"<<++cas<<": "<<Ans<<endl;
}
int main(){
int t;
scanf("%d",&t);
while(t--)solve();
return 0;
}
页:
[1]