您的位置: 首页  >  IT文章  >  【思维】三元环计数+鸽笼定理/贪心——LEETCODE 游乐园的游览计划 好题

【思维】三元环计数+鸽笼定理/贪心——LEETCODE 游乐园的游览计划 好题

分类: IT文章 • 2022-07-19 20:33:36

这题真的不错，有cf 的感觉

三元环计数：这题要先把三元环统计出来 https://www.cnblogs.com/Dance-Of-Faith/p/9759794.html

贪心：以v为顶点,把所有包含v的三元环统计出来，然后取权值最大的三个三元环t1,t2,t3，可以确定v为顶点的策略中至少有这三个中的一个(鸽笼定理，或者随便想想一定是这样)

　　　所以可以枚举前三个三元环，再枚举另一个三元环，设v有K个三元环，那么复杂度就是O(3K)

　　    由于所有三元环个数为O(m^1.5)，所以总复杂度也是这个

ps:在class内自定义sort的cmp函数，要用lambda表达式来写 关于lambda的使用以及捕获列表：https://blog.csdn.net/jlusuoya/article/details/75299096

class Solution {
public:
    #define N 10005
    vector<int>G[N];
    int id[N],rank[N],n,vis[N];
    int d[N],val[N];
    struct Circle{int a,b,c;};
    vector<Circle>s[N];

    inline int calc(Circle a,Circle b){
        int res=val[a.a]+val[a.b]+val[a.c]+val[b.a]+val[b.b]+val[b.c];
        if(a.a==b.a)res-=val[b.a];
        if(a.b==b.a)res-=val[b.a];
        if(a.c==b.a)res-=val[b.a];

        if(a.a==b.b)res-=val[b.b];
        if(a.b==b.b)res-=val[b.b];
        if(a.c==b.b)res-=val[b.b];
        
        if(a.a==b.c)res-=val[b.c];
        if(a.b==b.c)res-=val[b.c];
        if(a.c==b.c)res-=val[b.c];
        return res;
    }

    int maxWeight(vector<vector<int>>& edges, vector<int>& value) {
        n=value.size();    
        for(int i=0;i<n;i++)id[i]=i,val[i]=value[i];
        for(auto e:edges){
            int u=e[0],v=e[1];
            d[u]++,d[v]++;
        }

        sort(id,id+n,[&](int &a,int &b){
            if(d[a]==d[b])return a>b;
            return d[a]>d[b];
        });
        for(int i=0;i<n;i++)rank[id[i]]=i;

        for(auto e:edges){
            int u=e[0],v=e[1];
            if(rank[u]<rank[v])swap(u,v);
            G[u].push_back(v);
        }
        for(int i=0;i<n;i++){
            for(auto j:G[i])vis[j]=1;
            for(auto j:G[i])
                for(auto k:G[j])
                    if(vis[k]==1){
                        Circle t=(Circle){i,j,k};
                        s[i].push_back(t);
                        s[j].push_back(t);
                        s[k].push_back(t);
                    }
            for(auto j:G[i])vis[j]=0;
        }

        int ans=0;
        for(int i=0;i<n;i++){
            sort(s[i].begin(),s[i].end(),[&](Circle &a,Circle &b){
                int res1=val[a.a]+val[a.b]+val[a.c],res2=val[b.a]+val[b.b]+val[b.c];
                return res1>res2;
            });
            int j=s[i].size();
            if(j>=1){
                for(int k=0;k<j;k++)
                    ans=max(ans,calc(s[i][0],s[i][k]));
            }
            if(j>=2){
                for(int k=0;k<j;k++)
                    ans=max(ans,calc(s[i][1],s[i][k]));
            }
            if(j>=3){       
                for(int k=0;k<j;k++)
                    ans=max(ans,calc(s[i][2],s[i][k]));
            }
        }

        return ans;
    }
};

相关推荐