京东 cpp研发第二题 考试安排 图论解法 POJ1419

这个题目直接删掉链接人数最多的人的策略是错的,不仅仅是字典序的问题,连数目都可能是错的,大家可以自己多试试n==3的情况 构造多种不同的边数。
下面给出网上参考的代码给出的题解。题目 源自于 POJ1419 Graph Coloring 
这个题解获得的最少删除数目一定是对的,但是由于无法提交所以没办法验证是否可以通过字典序的要求。

正确解法 图论最大独立集  算法代码参照网络改进为本题要求后代码如下,思路需要百度学习。
#include<bits/stdc++.h>

using namespace std;
const int N = 505;
const int M = 100005;
bool w[N][N];
bool use[N];
bool bestx[N];
int cn,bestn,p,e;

void dfs(int x){
    bool flag;
    if(x>p){
        bestn=cn;
        for( int i=1; i<=p; i++)
            bestx[i]=use[i];
        return ;
    }
    flag=true;
    for( int i=1; i<x; i++){
        if(use[i]&&!w[i][x]){
            flag=false;
            break;
        }
    }
    if(flag){
        cn++;
        use[x]=true;
        dfs(x+1);
        cn--;
        use[x]=false;
    }
    if(cn+p-x>bestn){
        dfs(x+1);
    }
}

int main()
{
    int u,v;
    memset(w,true,sizeof(w));
    memset(use,false,sizeof(use));
    memset(bestx,false,sizeof(bestx));
    scanf("%d%d",&p,&e);
    p=p*2;
    for(int i=0; i<e; i++)
    {
        scanf("%d%d",&u,&v);
        w[u][v]=false;
        w[v][u]=false;
    }
    cn=bestn=0;
    dfs(1);
    printf("%d\n",p-bestn);
    for (int i=1; i<=p; i++)
        if(!bestx[i])printf("%d ",i);
    printf("\n");
    return 0;
}


#京东##笔试题目##秋招#
全部评论
嗯。修改了文章的一些表述,顶起来,欢迎各位交流思路
点赞 回复 分享
发布于 2019-08-24 22:17
我是先对数组进行排序,按照第一个排序,如果相同按照第二个排序,然后对数组进行判断,直接走到第一个数字不相同的位置,对第二个数字判断是否相同以及判断字典序,如果都不相同就删除第一个数字
点赞 回复 分享
发布于 2019-08-24 22:34
不知道对不对,反正没有写出来
点赞 回复 分享
发布于 2019-08-24 22:34

相关推荐

#牛客AI配图神器#和波主熟的朋友们都知道,波主真的很挺贪玩的哈哈哈哈很少看八股,也不爱看。。可能你们现在拷打波主八股会支支吾吾...回想我的面试,似乎都是围绕着我会的地方问,大概是最近和宿佬还有学长学到的引导面试罢...注意,此文只适合对面试技巧提升,并不是说可以不学八股啊喂!!回忆本人的面试经验,面试官刚拿到你的简历,对你是一无所知的,那其实他会根据印象深的东西对你进行提问,所以我们在简历方面可以做一个引导。面试开头是很正常的自我介绍,很多人会觉得随便说一下就好,但其实我们可以在这里也做一个引导的,而且多说一点也可以给面试官时间看你的简历,所以这里也可以准备一下。然后就是具体提问了,对实习...
nokotan:佬tql,还很谦虚。个人决定佬说得很对,要有意把面试官提问引导到简历项目上,但前提是自己对项目一定要熟悉。项目的需求背景、难点痛点、已有方案的不足、解决方案的实现都得有认知,虽然我们实习大多数是打杂,但是不影响我们偷文档学业务。只要能把上面几个点做到自圆其说,那基本就有6、7成把握了
点赞 评论 收藏
分享
ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
评论
7
18
分享

创作者周榜

更多
牛客网
牛客企业服务