[Codeforces Round #508 (Div. 2)][Codeforces 1038E. Maximum Matching]

前几天给舍友讲这题的时候感觉挺有意思的，就贴上来吧...

题目大意：有\(n\)个棒子，每个条两端有颜色\(c1,c2\)以及他的价值\(v\)，要求选取若干个棒子拼接起来（要求连接处的颜色相同，棒子可以反转），求最大价值总和。

题解：设\(c1==c2\)的为同色棒子，反之为异色

　　　可以发现偶数个异色棒子可以拼为一个长长的同色棒子，奇数个则可以拼为一个长长的异色棒子，因此可以预处理\(F[i][j]\)表示若将所有\((i,j)\)当做异色棒子来用所能得到的价值，\(G[i][j]\)表示当做同色棒子来用所能得到的价值。显然他们的值为所有颜色为\((i,j)\)的价值总和\(-k\cdot\)颜色为\((i,j)\)的最小价值，k等于0或1，由当前颜色的数目决定。

　　　对于同色的棒子，可以发现，若当前已经拼好的棒子里颜色\(c\)出现过，则可以将所有颜色为\(c\)的同色棒子塞进去以增加答案。

　　　接下去就是直接暴力DFS了，枚举起点的颜色，然后暴力考虑可以接哪些颜色，每次进入下一层的时候更新一次答案。更新答案就按照上面所说的那样，判断哪些颜色出现过，并将所有包含此颜色的异色棒子当做同色棒子来用塞进去。这里要注意一点，虽然塞进去的时候是当做同色来塞，但这种操作可能会导致新出现了一种颜色，而新颜色的出现可能还会导致答案的增加（即有包含新颜色的棒子）。因此这样子的操作还要再进行若干次，3次是肯定够的。最后再把所有已出现颜色的同色棒子加入就好了。

　　　由于颜色组合只有10种（(1,2)和(2,1)算一种），因此DFS的复杂度不会超过\(O(4^{10})\)，再乘上update的复杂度则为\(O(4^{13})\)，水过去是没有压力的

代码中将颜色对\((c1,c2)\)进行了标号处理

#include<bits/stdc++.h>

using namespace std;

#define N 101

int n,s[N],cnt[N],m[N],F[N],G[N],c1,c2,v,ans;

bool x[][],f[];

void update()

{

    bool g[],X[][];

    for(int i=;i<=;i++)g[i]=f[i];

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

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

        X[i][j]=x[i][j];

    int res=;

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

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

        if(x[i][j])res+=F[i*+j];

    for(int _=;_<;_++)

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

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

        if(!X[i][j] && (g[i]||g[j]) && cnt[i*+j]>)

          res+=G[i*+j],X[i][j]=true,g[i]=true,g[j]=true;

    for(int i=;i<=;i++)if(g[i])res+=s[i];

    ans=max(ans,res);

}

int get(int i,int j){if(i>j)swap(i,j);return i*+j;}

void dfs(int i)

{

    update();

    for(int j=;j<=;j++)

      if(!x[i][j] && cnt[get(i,j)])

        x[i][j]=x[j][i]=f[j]=true,dfs(j),x[i][j]=x[j][i]=f[j]=false;

}

int main()

{

    memset(m,0x3f,sizeof(m));

    scanf("%d",&n);

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

      {

      scanf("%d%d%d",&c1,&v,&c2);

      if(c1==c2){s[c1]+=v;continue;}

      if(c1>c2)swap(c1,c2);

      int id=c1*+c2;

      cnt[id]++,m[id]=min(m[id],v),s[id]+=v;

      }

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

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

        {

        int id=i*+j;

        if(cnt[id])F[id]=cnt[id]&?s[id]:(s[id]-m[id]);

        G[id]=cnt[id]&?(s[id]-m[id]):s[id];

        }

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

      f[i]=true,dfs(i),f[i]=false;

    return printf("%d\n",ans),;

}

巴特西

[Codeforces Round #508 (Div. 2)][Codeforces 1038E. Maximum Matching]

最新文章

热门文章