HDU 1068 Girls and Boys 二分图最大独力集字符串

HDU 1068 Girls and Boys 二分图最大独立集字符串

独立集是指两两之间没有边的顶点集合。顶点数目最多的集合称为最大独立集。

二分图最大独立集 = 顶点数 - 二分图最大匹配。

所以这题在于解决二个问题：

1、求二分图的最大匹配。

由于左右两个集合是同一集合，不分男女。所以，理论上讲存在0到3，就一定存在3到0。刚开始的想法是只将0到3记起来，

3到0就不记录了。这样在求最大匹配是可以少点计算。可是却WA了！不解。我还是觉得这种思路没错，并且可以减少时间。

个人怀疑是数据的问题了。

2、输入的每组数据可以看成是一个字符串。然后在处理之。当然，这题不看成字符串也是可以的。因为数组数据的“：”、

“（）”的位置是固定的，那么就可以一个一个数来输入了。

AC代码：2871MS

#include&lt;iostream&gt;using namespace std;const int MAX=500;   //最多人数const int help[]={1,10,100,1000,10000};  //辅助计算的数组bool map[MAX][MAX];bool used[MAX];int link[MAX];int n;char *tmp;void deal(char *a)  //处理输入的字符串，不是0到9的字符全赋为'\0'{int i,len=strlen(a);for(i=0;i&lt;len;i++){if(!(a[i]&gt;='0' && a[i]&lt;='9')){a[i]='\0';}}}int calculate(char *a)   //计算字符串的值，该字符串全由数字组成{int len=strlen(a);int num=0;for(int i=len-1;i&gt;=0;i--){num+=help[len-i-1]*(a[i]-'0');}return num;}void storeMap()   //存储二分图{int i,j,k,row,col;char ch[MAX*2];memset(map,false,sizeof(map));getchar();for(i=1;i&lt;=n;i++){gets(ch);   //获取整行，带空格deal(ch);tmp=ch;row=calculate(tmp);  //计算二分图的左顶点while(*tmp!='\0')tmp++;while(*tmp=='\0')tmp++;k=calculate(tmp);   //计算左顶点关联的右顶点数while(*tmp!='\0')tmp++;for(j=0;j&lt;k;j++){while(*tmp=='\0')tmp++;col=calculate(tmp);  //二分图右顶点while(*tmp!='\0')tmp++;//if(!map[col][row])   map[row][col]=true;   //true表示左右顶点关联}}}bool can(int t)  //确定是否存在增广路径{for(int i=0;i&lt;n;i++){if(!used[i] && map[t][i]){used[i]=true;if(link[i]==-1 || can(link[i])){link[i]=t;return true;}}}return false;}int maxMatch(){int num=0;memset(link,0xff,sizeof(link));for(int i=0;i&lt;n;i++)   //从每一左顶点出发寻找增广路径{memset(used,false,sizeof(used));if(can(i)) num++;}return num;}int main(){while(cin&gt;&gt;n){storeMap();cout&lt;&lt;n-maxMatch()/2&lt;&lt;endl;}return 0;}

HDU 1068 Girls and Boys 二分图 最大

热点推荐

HDU 1068 Girls and Boys 二分图最大