[ABC229F] Make Bipartite-图论+DP+环形

wflengxuenong · 2024-01-05 09:14:57 · 个人记录

题目大意：

给定一个类似从中心的切三角形西瓜的图，你删去一些边，使图成为二分图，且删去边权和最小。

做法：

图论转环形dp

最小删边数,保留的最大。不断增加

假设0点染0色

f[i][0/1]代表处理1..i个点，i个点与染什么颜色。 从离散的点开始加边。

确定起点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+9; 
ll a[N],b[N],n,f[N][2],ans,s=0; 
void work(int flag,ll x){
    memset(f,-32,sizeof(f)); //初始化，求最大值用最小值初始化。（写错丢分） 
    f[1][flag]=x;//不能与0点相连的  
    for(int i=2; i<=n; ++i)
    {
        f[i][0] = max(f[i-1][0], f[i-1][1] + b[i-1]);//可以与染1色的相连 
        f[i][1] = max(f[i-1][0] + b[i-1] , f[i-1][1]) + a[i];//可以与染0的i-1点相连。还可以与0点相连 
    }
    return ;
} 
int main(){

    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s+=a[i];
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]),s+=b[i];
    work(0,0);
    ans=max(f[n][0],f[n][1]+b[n]);
    work(1,a[1]);
    ans=max(ans,max(f[n][1],f[n][0]+b[n]));

    cout<<s-ans<<endl;  
}