Cat VS Dog
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 768 Accepted Submission(s): 258
Problem Description
The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child's like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa.
Now the zoo administrator is removing some animals, if one child's like-animal is not removed and his/hers dislike-animal is removed, he/she will be happy. So the administrator wants to know which animals he should remove to make maximum number of happy children.
Input
The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.
Next P lines, each line contains a child's like-animal and dislike-animal, C for cat and D for dog. (See sample for details)
Output
For each case, output a single integer: the maximum number of happy children.
Sample Input
1 1 2
C1 D1
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
Sample Output
1
3
Hint
Case 2: Remove D1 and D2, that makes child 1, 2, 3 happy.
Source
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3829
因为只有喜欢C讨厌D的人和喜欢D讨厌C的人之间才会产生矛盾，所以两者对称。就在讨厌、喜欢同一种的两人之间建边。
简单的一种方法是对于喜欢C或者D的一个人进行标记，增广时只从这些点开始增广，从而可以防止重复增广。
图建好了，Hungary即可。各种初始化都别忘了！！！
这道题其实就是求最大独立集，即全集-最小覆盖集（最大匹配）。
/*
Coded By BUPT-[aswmtjdsj] @ Penalty in 915
*/
/*
Bipartied Map Max Match
Because anyone either likes C and hates D,or likes D and hates C.
So the interruption between two people only exists in one's like equals another hate
and mark one person if he likes C (or D is ok too.),cause they are symmetrical(mark them and dfs just from them in order not to duplicate augment edges
then ans is the number of people minus the max match
MIND : INITIALIZATION like[] . vis[] . match[] . map[]..
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 505
bool map[maxn][maxn];
int match[maxn];
bool vis[maxn];
char str[maxn][3][5];
int like[maxn];
int N,M,P;
bool find(int x)
{
for(int i = 1;i <= P;i++)
{
if(map[x][i] && !vis[i])
{
vis[i] = true;
if(!match[i] || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d %d %d",&N,&M,&P) == 3)
{
memset(map,0,sizeof(map));
memset(like,0,sizeof(like));
for(int i = 1;i <= P;i++)
{
scanf("%s %s",str[i][0],str[i][1]);
if(str[i][0][0] == 'C')
like[i] = 1;
for(int j = 1;j < i;j++)
{
if(!strcmp(str[j][0],str[i][1]) || !strcmp(str[j][1],str[i][0]))
map[i][j] = map[j][i] = 1;
}
}
int ans = 0;
memset(match,0,sizeof(match));
for(int i = 1;i <= P;i++)
{
memset(vis,0,sizeof(vis));
if(like[i] && find(i))
ans++;
}
printf("%d\n",P - ans);
}
}
Asteroids
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 7687 | | Accepted: 4089 |
Description
Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.
Input
* Line 1: Two integers N and K, separated by a single space.
* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.
Output
* Line 1: The integer representing the minimum number of times Bessie must shoot.
Sample Input
3 4
1 1
1 3
2 2
3 2
Sample Output
2
Hint
INPUT DETAILS:
The following diagram represents the data, where "X" is an asteroid and "." is empty space:
X.X
.X.
.X.
OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).
Source
题目链接：
http://poj.org/problem?id=3041所谓矛盾建图：
因为shooting方式只有两种，按行射和按列射。所以存在矛盾两种射法只存在于行列之间，则有交点的行列射连边。求得最大匹配则为最少的射击次数。
仔细想想其中道理，选中的一个匹配边的含义是什么？因为行列射之间存在矛盾（都选则有浪费），那么这一对行列射中只选择行射或者列射。
考虑这种情况:
XXX
..X
..X
建图为1-1,1-2,1-3,2-3,3-3...
最后的最大匹配数为2.而且无论这两个匹配连接的行列射是什么，其中必然有一个行射为1，一个列射为3，也即，选择行射1，列射3，这两种射，可以得到最小射击次数。
但这与我们所知不符，
之前的我实在是太naive了！！！！这题就是明明白白的
最小点覆盖！！！
所谓这类模型的大概描述：某种关系图中有两类物体，A类物体a与B类物体b之间存在连接，存在连接表示这两者只能选其一，那么给出m组连接，求出最少需要选择多少个A以及B类物体，可以让每个连接的某一端点被覆盖。（在大部分这类题目里面，这个条件就保证了，所有约束条件被满足，即连接为约束，但单点被满足即为个体被满足。）
而根据Konig定理，最小点覆盖＝二分图最大匹配。详见，Matrix67对于该定理的证明
http://www.matrix67.com/blog/archives/116，根据他的证明，对于Hungary算法稍加改动，即可求出最小点覆盖的解集。
以下各题目基本可以yy成此类模型，A类集合中的点和B类集合中的点对于某一约束存在连接，问最少选取几个两类中的点可以让所有约束被满足。（选择一个点，可以满足所有与它有关的约束，根据此性质可以yy出大部分题目的建模。）
差不多以上，即为目前的理解。2011-07-23，有待修正。
题目链接：
http://poj.org/problem?id=1325Machine Schedule
| Time Limit: 1000MS | | Memory Limit: 10000K |
| Total Submissions: 7481 | | Accepted: 3143 |
Description
As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ..., mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, ... , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input
The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.
The input will be terminated by a line containing a single zero.
Output
The output should be one integer per line, which means the minimal times of restarting machine.
Sample Input
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output
3
Source
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 105
bool map[maxn][maxn],vis[maxn];
int mac[maxn];
int n,m,k;
bool find(int x)
{
for(int i = 1;i <= m;i++)
{
if(map[x][i] && !vis[i])
{
vis[i] = true;
if(!mac[i] || find(mac[i]))
{
mac[i] = x;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d",&n) == 1 && n)
{
memset(map,0,sizeof(map));
memset(mac,0,sizeof(mac));
scanf("%d %d",&m,&k);
for(int i = 1;i <= k;i++)
{
int t,a,b;
scanf("%d %d %d",&t,&a,&b);
if(!a || !b)
continue;
map[a][b] = 1;
}
int ans = 0;
for(int i = 1;i <= n;i++)
{
memset(vis,0,sizeof(vis));
if(find(i))
ans++;
}
printf("%d\n",ans);
}
}
Muddy Fields
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 4604 | | Accepted: 1720 |
Description
Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass, the rain makes some patches of bare earth quite muddy. The cows, being meticulous grazers, don't want to get their hooves dirty while they eat.
To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field.
Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other.
Compute the minimum number of boards FJ requires to cover all the mud in the field.
Input
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.
Output
* Line 1: A single integer representing the number of boards FJ needs.
Sample Input
4 4
*.*.
.***
***.
..*.
Sample Output
4
Hint
OUTPUT DETAILS:
Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.
Source
poj链接：
http://poj.org/problem?id=2226
spoj链接：
https://www.spoj.pl/problems/MUDDY/代码：注意有t和没t的区别。。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 630
#define data 55
bool vis[maxn];
int mac[maxn];
bool map[maxn][maxn];
int r,c,cntx,cnty;
int conx[data][data],cony[data][data];
char old[maxn][maxn];
bool find(int x)
{
for(int i = 1;i <= cnty;i++)
{
if(!vis[i] && map[x][i])
{
vis[i] = true;
if(!mac[i] || find(mac[i]))
{
mac[i] = x;
return true;
}
}
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0;i < t;i++)
{
scanf("%d %d",&r,&c);
for(int i = 1;i <= r;i++)
for(int j = 1;j <= c;j++)
scanf(" %c",&old[i][j]);
memset(conx,0,sizeof(conx));
memset(cony,0,sizeof(cony));
memset(map,0,sizeof(map));
memset(mac,0,sizeof(mac));
cntx = cnty = 0;
for(int i = 1;i <= r;i++)
{
bool flag = false;
for(int j = 1;j <= c;j++)
{
if(old[i][j] == '*')
{
if(!flag)
{
conx[i][j] = ++cntx;
flag = true;
}
else
{
if(conx[i][j - 1] != 0)
conx[i][j] = cntx;
else
conx[i][j] = ++cntx;
}
}
}
}
for(int j = 1;j <= c;j++)
{
bool flag = false;
for(int i = 1;i <= r;i++)
{
if(old[i][j] == '*')
{
if(!flag)
{
cony[i][j] = ++cnty;
flag = true;
}
else
{
if(cony[i - 1][j] != 0)
cony[i][j] = cnty;
else
cony[i][j] = ++cnty;
}
}
}
}
for(int i = 1;i <= r;i++)
for(int j = 1;j <= c;j++)
if(conx[i][j] && cony[i][j])
map[conx[i][j]][cony[i][j]] = 1;
int ans = 0;
for(int i = 1;i <= cntx;i++)
{
memset(vis,0,sizeof(vis));
if(find(i))
ans++;
}
printf("%d\n",ans);
}
}
å