HDU - 1045 Fire Net （缩点建图+二分图）
Fire NetTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14784 Accepted Submission(s): 8936 Problem Description Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
Input The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.
Output For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.
Sample Input 4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ... .XX .XX 4 .... .... .... .... 0
Sample Output 5 1 5 2 4
Source Zhejiang University Local Contest 2001
Recommend |
这道题的话，看完之后就知道是个匹配问题，但是却不清楚如何建图，进行连接和匹配。
之后看了解析之后发现，可以将每一段横区间和列区间当作点，把可以相交的区间建立连接之后直接上匈牙利算法就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ***
{
int a = 0, b = 0;
};
*** id[6][6];
char map[6][6];
bool link[105][105];
bool vis[105];
int use[105];
int hcnt, rcnt ,n;
void dfsh(int x, int y) {
if (y <= n && map[x][y] == '.') {
id[x][y].a = hcnt;
dfsh(x, y + 1);
}
}void dfsr(int x, int y) {
if (x <= n && map[x][y] == '.') {
id[x][y].b = rcnt;
dfsr(x+1, y );
}
}
int found(int x)
{
for (int s = 1; s < rcnt; s++) {
if (link[x][s] && !vis[s]) {
vis[s] = 1;
if (use[s] == 0 || found(use[s])) {
use[s] = x;
return 1;
}
}
}
return 0;
}
int main()
{
memset(link, 0, sizeof(link));
ios::sync_with_stdio(0);
while (~scanf("%d", &n) && n)
{
memset(id, 0, sizeof(id));
memset(link, 0, sizeof(link));
memset(use, 0, sizeof(use));
hcnt = rcnt = 1;
for (int s = 1; s <= n; s++)
for (int w = 1; w <= n; w++)
cin >> map[s][w];
for (int s = 1; s <= n; s++)
for (int w = 1; w <= n; w++) {
if (map[s][w] == 'X') {
continue;
}
if (id[s][w].a == 0) {
dfsh(s, w);
hcnt++;
}
if (id[s][w].b == 0) {
dfsr(s, w);
rcnt++;
}
link[id[s][w].a][id[s][w].b] = 1;
}
int sum = 0;
for (int s = 1; s < hcnt; s++) {
memset(vis, 0, sizeof(vis));
if (found(s))sum++;
}
// cout << hcnt << " " << rcnt << endl;
printf("%d\n", sum);
}
}
投递完美世界等公司10个岗位 >
