Question

杭电 1373题 http://acm.hdu.edu.cn/showproblem.php?pid=1373

我的思路就是，首先找出与某一点所有不相邻的点，然后从这些不相邻的点中，去点相邻的点，剩下的就是任意两点之间都是不相邻的，可以共用一个频道。也就是求一个最大独立集合。或许是我求最大的时候，贪心不对，还是哪里错了，WR好几次了，望各位高手指点迷津。下面的我的代码
#include "stdio.h"
#include "string.h"
int main()
{
char ch;
int i,j,k;
int num,min;
int channel_adj[26][26],channel_unadj[26][26],mark[26];
while(scanf("%d",&num) == 1)
{
if(num == 0)
{
break;
}
getchar();
memset(channel_adj,0,sizeof(channel_adj));
for(i = 0; i < num; i ++)
{
ch = getchar();
j = ch -'A';
while((ch = getchar()) && ch != '\n')
{
if(ch != ':')
{
channel_adj[j][ch - 'A'] = 1;
}
}
}
for(i = 0; i < num; i ++)
{
for(j = 0; j < num; j ++)
{
if(channel_adj[i][j] == 0)
{
channel_unadj[i][j] = 1;
}
else
{
channel_unadj[i][j] = 0;
}
}
}
min = 0;
memset(mark,0,sizeof(mark));
for(i = 0; i < num; i ++)
{
if(mark[i] == 0)
{
for(j = 0; j < num; j ++)
{
if(i != j && channel_unadj[i][j] == 1)
{
if(mark[j] == 1)
{
continue;
}
for(k = j + 1; k < num; k ++)
{
if(channel_adj[j][k] == 1 && channel_unadj[i][k] == 1)
{
channel_unadj[i][k] = 0;
}
}
}
}
for(k = 0; k < num; k ++)
{
if(channel_unadj[i][k] == 1)
{
mark[k] = 1;
}
}
min ++;
}
}
if(min == 1)
{
printf("%d channel needed.\n",min);
}
else
{
printf("%d channels needed.\n",min);
}
}
return 0;
}

Answer 1

你这个代码太长了。我做了好久，写了个代码。可能代码不是很好。但算理解了这个题目吧？
我们也可以探讨下。嘿嘿！！
#include<iostream>
#include<vector>
using namespace std;
vector<int> v[26];
int n;
int tu()
{
int color[26],num[5],i,j,k,t=0;
memset(color,0,sizeof(color));
memset(num,0,sizeof(num));
for( i=0;i<n;i++)
{
for( j=1;j<5;j++)
{
int len=v[i].size();
for( k=0;k<len;k++)
{
if(color[v[i][k]]==j)
{
break;
}
}
if(k==len)
{
color[i]=j;
num[j]=1;
break;
}

}
}
for(i=1;i<5;i++)
{
if(num[i])
{
t++;
}
}
return t;
}
int main()
{
int d,i,j,m;
while(cin>>n&&n)
{
for( i=0;i<n;i++)
{
v[i].clear();
char s[26];
cin>>s;
m=strlen(s);
for( j=2;j<m;j++)
v[i].push_back(s[j]-'A');
}
d=tu();
if(d==1)
cout<<"1 channel needed."<<endl;
else cout<<d<<" channels needed."<<endl;
}
return 0;
}