hdu 4185 Oil Skimming (二分图最大匹配，匈牙利算法)
hdu 4185题目链接 题意：给出一个nn的字符maze,‘.’代表水，‘#’代表油田。 挖油的机器一次会挖两个相邻方块。要求是必须两块必须都是油，不然会有杂质。问最多能挖多少次。 思路：和那道用12的小矩形块填充是一个思路。根据奇偶性对点标号，然后建图，匈牙利，2A. 第一遍是dfs写错了一个变量QAQ.a
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月30日 星期一 12时53分34秒
4File Name :code/hdu/4185.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1000;
34int n;
35char maze[N][N];
36int f1[N][N],f2[N][N];
37int tot1;
38int tot2;
39int cnt;
40int link[N*N];
41bool vis[N*N];
42int head[N*N];
43struct Edge
44{
45 int v;
46 int nxt;
47}edge[N*N*2];
48
49void addedge( int u,int v)
50{
51 edge[cnt].v = v;
52 edge[cnt].nxt = head[u];
53 head[u] = cnt;
54 cnt++;
55}
56
57bool find( int u)
58{
59 for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
60 {
61 int v = edge[i].v;
62 //cout<<"u:"<<u<<" v:"<<v<<endl;
63 if (vis[v]) continue;
64 vis[v] = true;
65 if (link[v]==-1||find(link[v]))
66 {
67 link[v] = u;
68 return true;
69 }
70 }
71
72 return false;
73}
74int hungary()
75{
76 ms(link,-1);
77 int res = 0;
78 for ( int i = 1 ; i <= tot1 ; i++)
79 {
80 ms(vis,false);
81 if (find(i)) res++;
82 }
83 return res;
84}
85int main()
86{
87 #ifndef ONLINE_JUDGE
88 freopen("code/in.txt","r",stdin);
89 #endif
90
91 int T;
92 int cas = 0 ;
93 scanf("%d",&T);
94 while (T--)
95 {
96 ms(f1,0);
97 ms(f2,0);
98 tot1 = 0 ;
99 tot2 = 0 ;
100 cnt = 0 ;
101 ms(head,-1);
102
103 scanf("%d",&n);
104 for ( int i = 0 ; i < n ; i++)
105 scanf("%s",maze[i]);
106
107 for ( int i = 0 ; i < n ; i++)
108 for ( int j = 0 ; j < n ; j++)
109 {
110 if (maze[i][j]=='.') continue;
111 if ((i+j)%2==0)
112 {
113 f1[i][j] = ++tot1;
114 }
115 else
116 {
117 f2[i][j] = ++tot2;
118 }
119
120 }
121
122 // cout<<"tot1:"<<tot1<<endl;
123 // cout<<"tot2:"<<tot2<<endl;
124
125 for ( int i = 0 ; i < n ; i++)
126 for ( int j = 0 ; j < n; j++)
127 {
128 if (j+1<n&&maze[i][j]=='#'&&maze[i][j+1]=='#')
129 {
130 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
131 int v = (i+j+1)%2==0?f1[i][j+1]:f2[i][j+1];
132 if ((i+j)%2==1) swap(u,v);
133 v+=tot1;
134 addedge(u,v);
135 }
136 if (i+1<n&&maze[i][j]=='#'&&maze[i+1][j]=='#')
137 {
138 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
139 int v = (i+1+j)%2==0?f1[i+1][j]:f2[i+1][j];
140 if ((i+j)%2==1) swap(u,v);
141 v+=tot1;
142 addedge(u,v);
143 }
144 }
145
146 int ans = hungary();
147 printf("Case %d: %d\n",++cas,ans);
148
149
150 }
151
152
153 #ifndef ONLINE_JUDGE
154 fclose(stdin);
155 #endif
156 return 0;
157}