hdu 1068 Girls and Boys

15453 ワード

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2013    Accepted Submission(s): 876
   これは私が初めて二分図の問題を書いたので、最初は問題を読む時少しぼんやりしていましたが、それから大牛の指摘を得て、また二分図に関する本を読んで、やっと二分図について少し理解しました.
実は本題は主に最大の孤立点セットを求めます:最大の独立セット=点-最大のマッチング数;
   ただし、ボリュームは、ポイントセットを(A)(B)に分割するのではなく、ポイントセット全体から検索されるため、最大マッチング数を求める場合は最大マッチング数/2を求めるべきであることに注意すべきである.
実行コード:
 

  
    
1 #include < stdio.h >
2 #include < string .h >
3   int n;
4   int g[ 1000 ][ 1000 ];
5 int mark[ 1000 ],ym[ 1000 ];
6 int chk[ 1000 ];
7 int searchpath( int u)
8 {
9 int v;
10 for (v = 0 ;v < n;v ++ )
11 if (g[u][v] == 1 && ! chk[v])
12 {
13 chk[v] = 1 ;
14 if (ym[v] ==- 1 || searchpath(ym[v]))
15 {
16 ym[v] = u;mark[u] = 1 ;
17 return 1 ;
18 }
19 }
20 return 0 ;
21 }
22 int maxmatch()
23 {
24 int u,ret = 0 ;
25 memset(mark, 0 , sizeof (mark));
26 memset(ym, - 1 , sizeof (ym));
27 for (u = 0 ;u < n;u ++ )
28 if (mark[u] == 0 )
29 {
30 memset(chk, 0 , sizeof (chk));
31 if (searchpath(u))
32 ret ++ ;
33 }
34 return ret;
35 }
36 int main()
37 {
38 int i,j,s,c,a,b;
39 while (scanf( " %d " , & n) != EOF)
40 {
41 memset(g, 0 , sizeof (g));
42 for (j = 0 ;j < n;j ++ )
43 {
44 scanf( " %d: (%d) " , & a, & b);
45 for (i = 1 ;i <= b;i ++ )
46 {
47 scanf( " %d " , & c);
48 g[a][c] = 1 ;
49 }
50 }
51 printf( " %d
" ,n - maxmatch() / 2 );
52 }
53 return 0 ;
54 }
55