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

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

1. #include <iostream>
   
2. #include <cstring>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int ans,g[200][200],bz[200][200],d[200];
   
7. 
   
8. /* n the number of students
   
9. ** k how many students in a  round
   
10. ** s and t the start student
    
11. */
    
12. void dfs(int n,int k,int s,int t)
    
13. {
    
14.         if(s == t&& k != 0)
    
15.         {
    
16.                 if(k%2)
    
17.                 {
    
18.                         ans++;
    
19.                         d[t]=1;
    
20.                 }
    
21.                 return ;
    
22.         }       
    
23.        
    
24.         for(int i=1;i<=n;i++)
    
25.         {       
    
26.                 if(g[s][i]==1&&bz[s][i]==0&&d[i]==0)
    
27.                 {       
    
28.                         bz[s][i]=bz[i][s]=1;
    
29.                         dfs(n,k+1,i,t);         
    
30.                         bz[s][i]=bz[i][s]=0;
    
31.                 }
    
32.         }
    
33. }
    
34. 
    
35. int main()
    
36. {
    
37.         int n,m,a,b;
    
38.         while(cin>>n>>m)
    
39.         {
    
40.                 memset(g,0,sizeof(g));
    
41.                 memset(bz,0,sizeof(bz));
    
42.                 memset(d,0,sizeof(d));
    
43.                 for(int i=0;i<m;i++)
    
44.                 {
    
45.                         cin>>a>>b;
    
46.                         g[a][b]=g[b][a]=1;
    
47.                 }
    
48.                 ans=0;
    
49.                 for(int i=1;i<=n;i++)
    
50.                 {       
    
51.                         dfs(n,0,i,i);
    
52.                 }
    
53.                 if( (n-ans)%2 == 1)ans++;
    
54.                 cout<<ans<<endl;
    
55.         }
    
56.         return 0;
    
57. }

复制代码

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

Gw_love_VC.

自己顶一个

wangyexin

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

wangyexin

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int d[200],g[200][200];
   
5. 
   
6. int main()
   
7. {
   
8.         int n,m,a,b;
   
9.         while(cin>>n>>m)
   
10.         {
    
11.                 memset(d,0,sizeof(d));
    
12.                 memset(g,0,sizeof(g));
    
13.                 for(int i=0;i<m;i++)
    
14.                 {
    
15.                         cin>>a>>b;
    
16.                         d[a]++;
    
17.                         d[b]++;
    
18.                         g[a][b]=g[b][a]=1;
    
19.                 }
    
20.                 int s=0;
    
21.                 for(int i=1;i<=m;i++)
    
22.                 {
    
23.                         if(d[i]==2)
    
24.                         {
    
25.                                 for(int j=1;j<=m;j++)
    
26.                                 {
    
27.                                         if(g[i][j]==1)
    
28.                                         {
    
29.                                                 g[j][i]=0;       
    
30.                                                 d[j]--;
    
31.                                         }
    
32.                                 }       
    
33.                                 s++;
    
34.                         }       
    
35.                 }
    
36.                 cout<<s<<endl;
    
37.         }
    
38.         return 0;
    
39. }
    

复制代码

试试这个代码

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

                               
登录/注册后可看大图

试试这个代码

1. for(int i=1;i<=m;i++)
   
2.                 {
   
3.                         if(d[i]==2)
   
4.                         {
   
5.                                 for(int j=1;j<=m;j++)
   
6.                                 {
   
7.                                         if(g[i][j]==1)
   
8.                                         {
   
9.                                                 g[j][i]=0;        
   
10.                                                 d[j]--;//这里我明白 ，不明白d数组是干什么的
    
11.                                         }
    
12.                                 }        
    
13.                                 s++;
    
14.                         }        
    
15.                 }

复制代码

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

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

我是来领鱼币的