posts - 14,  comments - 11,  trackbacks - 0

又一个二分图!其实对于这个题,关键是看你怎样建立二分图!
我比较偷懒,就用了一个黑白染色。题目意思很简单,就是要用多少个圆圈完*,当然每个圆只能圈两个*;
具体看代码吧,懒得写了,一个早上,还没吃饭呢?

 1 #include <iostream>
 2 using namespace std;
 3 bool map[500][500];
 4 bool vi[500];
 5 int link[500];
 6 int n,h;
 7 int x[4]={0,0,1,-1};
 8 int y[4]={1,-1,0,0};
 9 bool dfs(int v)
10 {
11      for (int i=1;i<=n;i++)
12      {
13          if (map[v][i]&&!vi[i])
14          {
15             vi[i]=true;
16             if (link[i]==0||dfs(link[i]))
17             {
18                link[i]=v;
19                return true;
20             }
21          }
22      }
23      return false;
24 }
25 int com()
26 {
27     int sum=0;
28     for (int i=1;i<=h;i++)
29     {
30         memset(vi,0,sizeof(vi));
31         if (dfs(i))sum++
32     }
33     return sum;
34 }
35 int main()
36 {
37     char a[50][16];
38     int b[50][16],c[50][16];
39     int m,k,i,j;
40     int t;
41     cin>>t;
42     while (t--)
43     { 
44           cin>>m>>k;
45           n=0,h=0;
46           memset(map,0,sizeof(map));
47           memset(link,0,sizeof(link));
48           memset(b,0,sizeof(b));
49           for (i=1;i<=m;i++)
50           for (j=1;j<=k;j++)
51           {
52               cin>>a[i][j];
53           }
54           h=0,n=0;
55           for (i=1;i<=m;i++)
56           for (j=1;j<=k;j++)
57           if (a[i][j]=='*')
58           {
59               if ((i+j)%2==0)b[i][j]=++h;
60               else b[i][j]=++n;
61           }
62           int dx,dy;
63           for (i=1;i<=m;i++)
64           for (j=1;j<=k;j++)
65           if  (a[i][j]=='*'&&(i+j)%2==0)
66           {
67               for (int l=0;l<4;l++)             
68               {
69                   dx=x[l]+i;
70                   dy=y[l]+j;
71                   if (a[dx][dy]=='*')
72                   map[b[i][j]][b[dx][dy]]=1;           
73               }                                    
74           }
75           cout<<h+n-com()<<endl;
76     }
77 return 0;
78 }
79 
posted on 2011-04-05 10:46 路修远 阅读(1168) 评论(0)  编辑 收藏 引用 所属分类: 路修远

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

转载,请标明出处!谢谢~~

常用链接

留言簿(1)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

  • 1. re: HDU 2433 最短路
  • @test
    的确这组数据应该输出20的
  • --YueYueZha
  • 2. re: HDU 2433 最短路
  • 这方法应该不对。 看下面这组数据
    4 4
    1 2
    2 3
    3 4
    2 4

    画个图,删去最后一条边 2 4 后的结果应该是20,但是此方法的输出是19
  • --test
  • 3. re: HDU 2433 最短路
  • ans = ans + sum_u + sum_v - sum[u] - sum[v],
    这个公式不是很理解啊,不知道博主怎么想的啊,谢谢咯
  • --姜
  • 4. re: HDU 2433 最短路
  • @attacker
    the i-th line is the new SUM after the i-th road is destroyed
  • --路修远
  • 5. re: HDU 2433 最短路
  • 你这样可以AC????删除<U,V>不仅改变 u,v最短路啊、、、求解
  • --attacker

阅读排行榜

评论排行榜