HDU5772 String problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 614    Accepted Submission(s): 282

Problem Description

This 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[x]=0,kx=0cost[x]=ax∗(kx−1)+bx,kx≠0

TotalCost=∑i=09cost[i]

The 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[i]][id[j]];
     }
}

id[i] 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.

 

Input

The 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[i][j]<=50

 

Output

Each test output one line “Case #x: y” , where x is the case number ,staring from 1. y is the Maximum score.

 

Sample Input

1 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 0

 

Sample Output

Case #1: 3

Hint

we can choose “15”，id[]={1,3} then Value=w[1][3]+w[3][1]=7, Total_Cost=2+2=4，Score=7-4=3

 

Author

FZU

 

Source

2016 Multi-University Training Contest 4

 

Recommend

wange2014

 

给定一个只由0~9数字组成的串，要求从其中选出一个价值最大的子序列

网络流 最大权闭合子图

连边有点复杂，本质上还是个最大权闭合子图。

可以看出主要关系有三种：

1、选点i和j，可以得到的组合权值

2、选点的代价，代价随着相同数字使用次数累计。

3、子序列包含某个数字就需要付出的代价

如果把第2类点的权值都设成a[i]，各自容量为1，第3类点的权值设成-(b[i]-a[i])，各自容量为INF，选2就必须选对应的3，那么代价问题就解决了。

割1舍弃收益，割2+3舍弃数字，显然是一个最大权闭合子图问题。

/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int mxn=100010;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int min(int a,int b){return a<b?a:b;}
struct edge{
    int v,nxt,f;
}e[mxn<<1];
int hd[mxn],mct=1;
void add_edge(int u,int v,int w){
    e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=w;hd[u]=mct;return;
}
void insert(int u,int v,int w){
    add_edge(u,v,w);add_edge(v,u,0);
    return;
}
int S,T;
int d[mxn];
queue<int>q;
bool BFS(){
    memset(d,0,sizeof d);
    q.push(S);d[S]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(!d[v] && e[i].f){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[T];
}
int DFS(int u,int lim){
    if(u==T)return lim;
    int f=0,tmp;
    for(int i=hd[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){
            e[i].f-=tmp;
            e[i^1].f+=tmp;
            lim-=tmp;
            f+=tmp;
            if(!lim)return f;
        }
    }
    d[u]=0;
    return f;
}
int Dinic(){
    int res=0;
    while(BFS()){res+=DFS(S,INF);}
    return res;
}
int n,m,ed,cnt;
char s[200];
int mp[120][120];
int a[11],b[11];
void Build(){
    ed=n*(n-1)/2;cnt=0;
    S=0;T=ed+n+10+1;
    int i,j;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            ++cnt;
            insert(S,cnt,mp[i][j]+mp[j][i]);
            insert(cnt,ed+i,INF);
            insert(cnt,ed+j,INF);
        }
    }
    for(i=1;i<=n;i++){
        int c=s[i]-'0'+1;
        insert(ed+i,T,a[c-1]);
        insert(ed+i,ed+n+c,INF);
    }
    for(i=0;i<=9;i++){
        int u=ed+n+i+1;
        insert(u,T,b[i]-a[i]);
    }
    return;
}
void init(){
    memset(hd,0,sizeof hd);mct=1;
    return;
}
int cas;
int main(){
    int i,j,u,v;
    cas=read();int cct=0;
    while(cas--){
        int ans=0;
        init();
        n=read();
        scanf("%s",s+1);
        for(i=0;i<=9;i++){a[i]=read();b[i]=read();}
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                mp[i][j]=read(),ans+=mp[i][j];
        Build();
        ans-=Dinic();
        printf("Case #%d: %d
",++cct,ans);
    }
    return 0;
}