论坛 › 数据结构与算法 › 求教呀。。。是关于图的问题 求思路。。。求围观

Gw_love_VC. 发表于 2013-2-2 11:31:54

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

在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个人不能参加。
我自己的思路：从任意一个数开始遍历如果第四次能够回到原来的数字就计数一次，最后计得的数就是最少要有几个人不能参加。形象的说能构成一个三角形就计数一次。
语言表达有限。。。{:5_111:}
求思路。。。求围观。。。

wangyexin 发表于 2013-2-2 11:31:55

#include <iostream>
#include <cstring>

using namespace std;

int ans,g,bz,d;

/* n the number of students
** k how many students in around
** 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=1;
                }
                return ;
        }       
       
        for(int i=1;i<=n;i++)
        {       
                if(g==1&&bz==0&&d==0)
                {       
                        bz=bz=1;
                        dfs(n,k+1,i,t);       
                        bz=bz=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=g=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. 发表于 2013-2-2 12:08:18

自己顶一个{:5_103:}

wangyexin 发表于 2013-2-2 14:29:01

本帖最后由 wangyexin 于 2013-2-2 14:33 编辑

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

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

#include <iostream>
using namespace std;

int d,g;

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++;
                        d++;
                        g=g=1;
                }
                int s=0;
                for(int i=1;i<=m;i++)
                {
                        if(d==2)
                        {
                                for(int j=1;j<=m;j++)
                                {
                                        if(g==1)
                                        {
                                                g=0;       
                                                d--;
                                        }
                                }       
                                s++;
                        }       
                }
                cout<<s<<endl;
        }
        return 0;
}
试试这个代码

xitonggongchen 发表于 2013-2-2 14:54:21

顶一下，数据结构太难了

xitonggongchen 发表于 2013-2-2 17:11:38

再顶一下！

xitonggongchen 发表于 2013-2-2 17:17:32

赚点鱼币，多谢了

Gw_love_VC. 发表于 2013-2-2 19:54:38

xitonggongchen 发表于 2013-2-2 19:41 static/image/common/back.gif
赚取鱼币了喽

论坛有专门赚鱼币的地方大哥你赢了{:5_100:}

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

wangyexin 发表于 2013-2-2 14:52 static/image/common/back.gif
试试这个代码

有错误       ！！

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

本帖最后由 Gw_love_VC. 于 2013-2-3 11:10 编辑

wangyexin 发表于 2013-2-2 14:52 static/image/common/back.gif
试试这个代码
for(int i=1;i<=m;i++)
                {
                        if(d==2)
                        {
                              for(int j=1;j<=m;j++)
                              {
                                        if(g==1)
                                        {
                                                g=0;      
                                                d--;//这里我明白 ，不明白d数组是干什么的
                                        }
                              }      
                              s++;
                        }      
                }大哥能不能{:5_109:}
加点解释看不太懂还有 想问问 什么时候用邻接矩阵什么时候用邻接表{:5_93:}

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

牡丹花下死做鬼 发表于 2013-2-2 22:22 static/image/common/back.gif
有错误       ！！

求高见{:5_101:}

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

Gw_love_VC. 发表于 2013-2-3 10:56 static/image/common/back.gif
求高见

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

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

牡丹花下死做鬼 发表于 2013-2-3 11:26 static/image/common/back.gif
什么啊   我是初学者啊 只不过把你的代码复制下来在在编译是显示 有 错误我有看不出来 拿错了

{:5_97:}不是我写的   我的VS2008能通过不过OJ还这是通不过

wangyexin 发表于 2013-2-3 13:25:34

Gw_love_VC. 发表于 2013-2-3 11:29 static/image/common/back.gif
不是我写的   我的VS2008能通过不过OJ还这是通不过

OJ编译错误还是WA？

wangyexin 发表于 2013-2-3 13:28:38

Gw_love_VC. 发表于 2013-2-3 10:56 static/image/common/back.gif
大哥能不能
加点解释看不太懂还有 想问问 什么时候用邻接矩阵什么时候用邻接表

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

wangyexin 发表于 2013-2-3 13:44:05

编译错误是memset没头文件

y290176346 发表于 2015-9-18 16:49:45

我是来领鱼币的

查看完整版本: 求教呀。。。是关于图的问题 求思路。。。求围观