HDU5772 (最小割）

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)

　　要求最大化价值-代价。

题目分析

　　比较难想到的最大权闭合图模型。

　　昨天刚补完一道，今天又没想出来^~~

　　搬运官方题解：

参考程序

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define INF 2000000000
  8 #define V 6000
  9 #define E 100000
 10 int n,m,ans,dis[V],S,T;
 11 
 12 struct line{
 13     int u,v,c,nt;
 14 }eg[E];
 15 int lt[V],sum=1;
 16 
 17 void adt(int u,int v,int c){
 18     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; eg[sum].nt=lt[u]; lt[u]=sum;
 19 }
 20 
 21 void add(int u,int v,int c){
 22   //  printf("%d %d %d
",u,v,c );
 23     adt(u,v,c); adt(v,u,0);
 24 }
 25 
 26 void init(){
 27     memset(lt,0,sizeof(lt));
 28     sum=1; ans=0;
 29 }
 30 
 31 bool bfs(){
 32     memset(dis,0,sizeof(dis));
 33     dis[S]=1;
 34     queue<int> Q;
 35     Q.push(S);
 36     while (!Q.empty()){
 37         int u=Q.front();
 38         Q.pop();
 39         for (int i=lt[u];i;i=eg[i].nt){
 40             int v=eg[i].v;
 41             if (eg[i].c && !dis[v]){
 42                 dis[v]=dis[u]+1;
 43                 Q.push(v);
 44             }
 45         }
 46     }
 47     return dis[T]>0;
 48 }
 49 
 50 int dfs(int u,int flow){
 51     if (u==T) return flow;
 52     int res=0,f;
 53     for (int i=lt[u];i;i=eg[i].nt){
 54         int v=eg[i].v;
 55         if (eg[i].c&&dis[v]==dis[u]+1){
 56             f=dfs(v,min(flow-res,eg[i].c));
 57             res+=f;
 58             eg[i].c-=f;
 59             eg[i ^ 1].c+=f;
 60             if (flow==res) break;
 61         }
 62     }
 63     if (!res) dis[u]=-1;
 64     return res;
 65 }
 66 
 67 int dinic(){
 68     int sum=0;
 69     while (bfs()) sum+=dfs(S,INF);
 70     return sum;
 71 }
 72 
 73 int main(){
 74 
 75     int Tp,cas=0,cnt;
 76     char s[108];
 77     int a[20],b[20],w[108][108];
 78 
 79     scanf("%d",&Tp);
 80     while (Tp--){
 81         init();
 82         
 83         scanf("%d",&n);
 84         scanf("%s",s+1);
 85         for (int i=0;i<=9;i++) scanf("%d%d",&a[i],&b[i]);    
 86         for (int i=1;i<=n;i++)
 87             for (int j=1;j<=n;j++)
 88             {    
 89                 scanf("%d",&w[i][j]);
 90                 ans+=w[i][j];
 91             }
 92         S=0,T=n*(n-1)/2+n+10+1,cnt=0;
 93         for (int i=1;i<=n;i++)
 94             for (int j=i+1;j<=n;j++){
 95                 cnt++;
 96                 add(S,cnt,w[i][j]+w[j][i]);
 97                 add(cnt,n*(n-1)/2+i,INF);
 98                 add(cnt,n*(n-1)/2+j,INF);
 99             }
100         for (int i=1;i<=n;i++){
101             add(n*(n-1)/2+i,n*(n-1)/2+n+s[i]-'0'+1,INF);
102             add(n*(n-1)/2+i,T,a[s[i]-'0']);
103         }
104         for (int i=0;i<=9;i++)
105             add(n*(n-1)/2+n+i+1,T,(b[i]-a[i]));
106         n=T;
107         printf("Case #%d: %d
",++cas,ans-dinic());        
108     }
109 }

View Code