京东 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;
} 
蚂蚁集团公司福利 206人发布
