求教呀。。。是关于图的问题 求思路。。。求围观

Gw_love_VC.

在acm上看了个题。。。Forming teams题目提示要用到图、深度遍历的知识。 原题连接 http://acm.guet.edu.cn/problemset/problem/1101
梗概：有n个人到足球场踢足球，要分成两组。其中有m对人之间有矛盾，但是每个人最多和两个人之间有矛盾。
有矛盾的人不能在同一个队伍。问最少要有几个人不能参加。
栗子：  6个人到操场踢球，有6对矛盾，分别是1-2 , 2-3，3-1，4-5 ,5-6 ,6-4。现在最少有2个人不能参加。
我自己的思路：从任意一个数开始遍历如果第四次能够回到原来的数字就计数一次，最后计得的数就是最少要有几个人不能参加。形象的说能构成一个三角形就计数一次。
语言表达有限。。。
求思路。。。求围观。。。

wangyexin

#include <iostream>
#include <cstring>

using namespace std;

int ans,g[200][200],bz[200][200],d[200];

/* n the number of students
** k how many students in a  round 
** s and t the start student
*/
void dfs(int n,int k,int s,int t)
{
        if(s == t&& k != 0)
        {
                if(k%2)
                {
                        ans++;
                        d[t]=1;
                } 
                return ;
        }        
        
        for(int i=1;i<=n;i++)
        {        
                if(g[s][i]==1&&bz[s][i]==0&&d[i]==0)
                {        
                        bz[s][i]=bz[i][s]=1;
                        dfs(n,k+1,i,t);         
                        bz[s][i]=bz[i][s]=0;
                }
        }
}

int main()
{
        int n,m,a,b;
        while(cin>>n>>m)
        {
                memset(g,0,sizeof(g));
                memset(bz,0,sizeof(bz));
                memset(d,0,sizeof(d));
                for(int i=0;i<m;i++)
                {
                        cin>>a>>b;
                        g[a][b]=g[b][a]=1;
                }
                ans=0;
                for(int i=1;i<=n;i++)
                {        
                        dfs(n,0,i,i);
                }
                if( (n-ans)%2 == 1)ans++;
                cout<<ans<<endl;
        }
        return 0;
}

算法：看有多少个人数为奇数的环，有多少个就要减去多少人，最后看剩下的是奇数还是偶数，奇数的话还要再减去一个

Gw_love_VC.

自己顶一个

wangyexin

如果一个人和2个人有矛盾 那么这个人就不能参加

wangyexin

#include <iostream>
using namespace std;

int d[200],g[200][200];

int main()
{
        int n,m,a,b;
        while(cin>>n>>m)
        {
                memset(d,0,sizeof(d));
                memset(g,0,sizeof(g));
                for(int i=0;i<m;i++)
                {
                        cin>>a>>b;
                        d[a]++;
                        d[b]++;
                        g[a][b]=g[b][a]=1;
                }
                int s=0;
                for(int i=1;i<=m;i++)
                {
                        if(d[i]==2)
                        {
                                for(int j=1;j<=m;j++)
                                {
                                        if(g[i][j]==1)
                                        {
                                                g[j][i]=0;        
                                                d[j]--;
                                        }
                                }        
                                s++;
                        }        
                }
                cout<<s<<endl;
        }
        return 0;
}

试试这个代码

xitonggongchen

顶一下，数据结构太难了

xitonggongchen

再顶一下！

xitonggongchen

赚点鱼币，多谢了

Gw_love_VC.

xitonggongchen 发表于 2013-2-2 19:41

                               
登录/注册后可看大图

赚取鱼币了喽

论坛有专门赚鱼币的地方  大哥你赢了

牡丹花下死做鬼

wangyexin 发表于 2013-2-2 14:52

                               
登录/注册后可看大图

试试这个代码

有错误       ！！

Gw_love_VC.

wangyexin 发表于 2013-2-2 14:52

                               
登录/注册后可看大图

试试这个代码

for(int i=1;i<=m;i++)
                {
                        if(d[i]==2)
                        {
                                for(int j=1;j<=m;j++)
                                {
                                        if(g[i][j]==1)
                                        {
                                                g[j][i]=0;        
                                                d[j]--;//这里我明白 ，不明白d数组是干什么的
                                        }
                                }        
                                s++;
                        }        
                }

大哥能不能
加点解释  看不太懂还有 想问问 什么时候用邻接矩阵什么时候用邻接表

Gw_love_VC.

牡丹花下死做鬼 发表于 2013-2-2 22:22

                               
登录/注册后可看大图

有错误       ！！

求高见

牡丹花下死做鬼

Gw_love_VC. 发表于 2013-2-3 10:56

                               
登录/注册后可看大图

求高见

什么啊   我是初学者  啊 只不过把你的代码复制下来在在编译是显示 有 错误  我有看不出来 拿错了

Gw_love_VC.

牡丹花下死做鬼 发表于 2013-2-3 11:26

                               
登录/注册后可看大图

什么啊   我是初学者  啊 只不过把你的代码复制下来在在编译是显示 有 错误  我有看不出来 拿错了

不是我写的   我的VS2008能通过  不过OJ还这是通不过

wangyexin

Gw_love_VC. 发表于 2013-2-3 11:29

                               
登录/注册后可看大图

不是我写的   我的VS2008能通过  不过OJ还这是通不过

OJ编译错误还是WA？

wangyexin

Gw_love_VC. 发表于 2013-2-3 10:56

                               
登录/注册后可看大图

大哥能不能
加点解释  看不太懂还有 想问问 什么时候用邻接矩阵什么时候用邻接表

个人感觉邻接矩阵比邻接表编码简单，只要能时间复杂度符合要求就用邻接矩阵，如果还要优化就考虑邻接表

wangyexin

编译错误是memset没头文件

y290176346

我是来领鱼币的