HDU5772 String problem 最大权闭合图+巧妙建图

时间：2021-03-14 05:30:51

题意：自己看吧（不是很好说）

分析：

网络流：最大权闭合子图。

思路如下：

首先将点分为3类

第一类：Pij 表示第i个点和第j个点组合的点，那么Pij的权值等于w[i][j]+w[j][i]（表示得分）

第二类：原串中的n个点每个点拆出一个点，第i个点权值为 –a[s[i]] （表示要花费）

第三类：对于10种字符拆出10个点，每个点的权值为  -(b[x]-a[x])

那么我们可以得到一个关系图 ，对于第一类中的点Pij，如果想要选择Pij，你就必须要选中第二类中的点i和j，对于第二类中的点如果你想选中第i个点，其对应的字符s[i]，那么就必须选中第三类中s[i] 对应的点，因为每个种类的点第一次选中时花费是b[s[i]]，而第二类中花费都是a[s[i]],一定要补上b[s[i]]-a[s[i]]，而且只需要补上一次。

得到上面的关系图后然后就是普通的最大权闭合子图问题,直接求解即可。

注：吐槽，我想说真的是神思路，加网络流大法好，我只想说没有刷过网络流24题的人伤不起啊

首先想会做这个题，必须会最大权闭合子图的概念，这个是网络流24题之一（多刷题就是好），但是就算是会了这个建图，也不一定会做这个题

虽然说这个题看数据范围什么的，限制条件这么多的，差不多能想到是网络流，但是伤在不会建图啊

这个题很巧妙的点，就是一个子序列的贡献是每两个不同点组成的，这是独立的，只和这两个元素有关，和序列的其它元素无关，这样每两个元素就可以虚拟一个点了

然后按照题解建成有向图，对于u-->v,选u必须选v 对于这种图的求最大方案，显然就是求最大权闭合图

如何建图，请见http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html（可以顺便把这个题做一下，是个裸题）

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int INF = 0x3f3f3f3f;

const int maxn=4e4+;

struct Edge

{

    int from,to,cap,flow;

    Edge(int u,int v,int c,int d):from(u),to(v),cap(c),flow(d) {}

};

struct dinic

{

    int s,t;

    vector<Edge>edges;

    vector<int>G[maxn];

    int d[maxn];

    int cur[maxn];

    bool vis[maxn];

    void init(){

      for(int i=;i<maxn;++i)G[i].clear();

      edges.clear();

    }

    bool bfs()

    {

        memset(vis,,sizeof(vis));

        queue<int>q;

        q.push(s);

        d[s]=;

        vis[s]=;

        while(!q.empty())

        {

            int x=q.front();

            q.pop();

            for(int i=; i<G[x].size(); i++)

            {

                Edge &e= edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to]=;

                    d[e.to]=d[x]+;

                    q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int dfs(int x,int a)

    {

        if(x==t||a==)return a;

        int flow=,f;

        for(int &i=cur[x]; i<G[x].size(); i++)

        {

            Edge &e=edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow))))

            {

                e.flow+=f;

                edges[G[x][i]^].flow-=f;

                flow+=f;

                a-=f;

                if(a==)break;

            }

        }

        return flow;

    }

    LL maxflow(int s,int t)

    {

        this->s=s;

        this->t=t;

        LL flow=;

        while(bfs())

        {

            memset(cur,,sizeof(cur));

            flow+=dfs(s,INF);

        }

        return flow;

    }

    void addedge(int u,int v,int c)

    {

        Edge x(u,v,c,),y(v,u,,);

        edges.push_back(x);

        edges.push_back(y);

        int l=edges.size();

        G[u].push_back(l-);

        G[v].push_back(l-);

    }

}solve;

int a[],b[],T,n,w[][],kase;

char s[];

int main(){

  scanf("%d",&T);

  while(T--){

     solve.init();

     scanf("%d%s",&n,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]);

     int cnt=,p=n*(n-)/;

     LL sum=;

     for(int i=;i<n;++i){

       for(int j=i+;j<=n;++j){

         ++cnt;

         if(w[i][j]+w[j][i]>){

          solve.addedge(,cnt,w[i][j]+w[j][i]);

          sum+=w[i][j]+w[j][i];

         }

         solve.addedge(cnt,p+i,INF);

         solve.addedge(cnt,p+j,INF);

       }

     }

     int t=cnt+n+;

     for(int i=;i<=n;++i){

      if(a[s[i]-''+]>)

       solve.addedge(cnt+i,t,a[s[i]-''+]);

       solve.addedge(cnt+i,cnt+n+s[i]-''+,INF);

     }

     for(int i=cnt+n+;i<=cnt+n+;++i)

        if(b[i-cnt-n]-a[i-cnt-n]>)

      solve.addedge(i,t,b[i-cnt-n]-a[i-cnt-n]);

     printf("Case #%d: %I64d\n",++kase,sum-solve.maxflow(,t));

  }

  return ;

}

相关文章