| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:0ms一发AC,不需要任何搜索,贴一发代码,四色定理直接染In Reply To:0ms一发AC,不需要任何搜索,贴一发代码,四色定理直接染 Posted by:danagi at 2015-08-13 12:00:58 > #include <stdio.h>
> #include <string.h>
> bool grid[26][26];
> int color[26];
> int lowbit(int x)
> {
> return x&(-x);
> }
> int getColorNum(int x)
> {
> switch(x)
> {
> case 0x1:return 1;
> case 0x2:return 2;
> case 0x4:return 3;
> case 0x8:return 4;
> }
> }
> int main()
> {
> char c;
> int n,ans,tmp;
> while(scanf("%d\n",&n)&&n)
> {
> ans=0;
> memset(grid,false,sizeof(grid));
> for(int i=0;i<n;++i)
> {
> getchar();
> getchar();
> while((c=getchar())!='\n')
> grid[i][c-'A']=true;
> color[i]=0xf;
> }
> for(int i=0;i<n;++i)
> {
> color[i]=lowbit(color[i]);
> tmp=getColorNum(color[i]);
> if(tmp>ans)
> ans=tmp;
> if(ans==4)
> break;
> for(int j=i+1;j<n;++j)
> if(grid[i][j])
> color[j]^=color[i];
> }
> ans==1?printf("%d channel needed.\n",ans):printf("%d channels needed.\n",ans);
> }
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator