套班子灾区、、、板子在手天下我有、、、
A - Fire Net
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.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.
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
把能匹配的行列分别编号，然后跑匈牙利。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 100;
int uN, vN;
bool used[maxn], g[maxn][maxn];
int lnk[maxn];
bool dfs(int u)
{
for(int v = 0; v < vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 0; u < uN; u++) {
memset(used, 0, sizeof used);
if(dfs(u)) res++;
}
return res;
}
int n;
char maze[10][10];
int a[10][10], b[10][10];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(scanf("%d", &n), n) {
rep(i, 0, n - 1) scanf("%s", maze[i]);
memset(g, 0, sizeof g);
memset(a, -1, sizeof a);
memset(b, -1, sizeof b);
bool f = false;
int p = -1;
rep(i, 0, n - 1) {
f = true;
rep(j, 0, n - 1) {
if(maze[i][j] == 'X') {
f = true;
continue;
}
if(f) {
p++; f = false;
}
a[i][j] = p;
uN = p + 1;
}
}
p = -1;
rep(j, 0, n - 1) {
f = true;
rep(i, 0, n - 1) {
if(maze[i][j] == 'X') {
f = true;
continue;
}
if(f) {
p++; f = false;
}
b[i][j] = p;
vN = p + 1;
}
}
//cout << uN << ' ' <<vN << endl;
rep(i, 0, n - 1) rep(j, 0, n - 1) {
if(a[i][j] >= 0 && b[i][j] >= 0) g[a[i][j]][b[i][j]] = true;
//cout << a[i][j] << ' ' << b[i][j] << ' ' << i << ' ' <<j <<endl;;
}
printf("%d\n", hungary());
}
return 0;
}
B - The Accomodation of Students
There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.
Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.
Calculate the maximum number of pairs that can be arranged into these double rooms.
Input
For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.
Proceed to the end of file.
Output
If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.
Sample Input
4 4 1 2 1 3 1 4 2 3 6 5 1 2 1 3 1 4 2 5 3 6
Sample Output
No 3
对图的每个子图bfs（dfs也差不多）染色分为二分图，如果染色成功就跑匈牙利匹配。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 250;
bool g[maxn][maxn];
int lnk[maxn];
int uN, vN;
bool used[maxn];
int col[maxn];
bool dfs(int u)
{
for(int v = 1; v <= vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= uN; u++) if(col[u] >= 0){//cout <<"u " << u << endl;
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return res / 2;
}
int n, m, ans;
//bool u[maxn], v[maxn];
queue<int> que;
bool ok(int s)
{
while(!que.empty()) que.pop();
col[s] = 1;
que.push(s);
while(!que.empty()) {
int h = que.front(); que.pop();//cout << s << ' ' <<h << endl;
rep(i, 1, n) if(g[h][i]) {
if(col[i] > 0) {
if(col[i] == col[h]) return false;
}
else {
col[i] = col[h] % 2 + 1;
que.push(i);
}
}
}
return true;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d", &n, &m)) {
uN = vN = n;
memset(g, 0, sizeof g);
bool f = true;
memset(col, -1, sizeof col);
rep(i, 1, m) {
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = 1;
g[b][a] = 1;
col[a] = col[b] == 0;
}
rep(i, 1, n) {
if(col[i] == 0 && !ok(i)) {
f = false;
break;
}
}
if(f) printf("%d\n", hungary());
else puts("No");
}
return 0;
}
C - Courses
Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions:
. every student in the committee represents a different course (a student can represent a course if he/she visits that course)
. each course has a representative in the committee
Your program should read sets of data from a text file. The first line of the input file contains the number of the data sets. Each data set is presented in the following format:
P N
Count1 Student1 1 Student1 2 ... Student1 Count1
Count2 Student2 1 Student2 2 ... Student2 Count2
......
CountP StudentP 1 StudentP 2 ... StudentP CountP
The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses . from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you'll find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N.
There are no blank lines between consecutive sets of data. Input data are correct.
The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.
An example of program input and output:
Input
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Output
YES NO
Sample Input
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Sample Output
YES NO
板子题。hungary()函数写法略有不同，原来的计数也一样。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 310;
int lnk[maxn];
int uN, vN;
bool g[maxn][maxn], used[maxn];
bool dfs(int u)
{
for(int v = 1; v <= vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= uN; u++) {
memset(used, false, sizeof used);
if(!dfs(u)) {
return false;
}
}
return true;
}
vector<int> data[maxn];
int cnt[maxn];
bool vis[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &uN, &vN);
memset(cnt, 0, sizeof cnt);
memset(g, 0, sizeof g);
rep(i, 1, uN) {
memset(vis, false, sizeof vis);
data[i].clear();
int n;
scanf("%d", &n);
while(n--) {
int m;
scanf("%d", &m);
// data[i].push_back(m);
// if(!vis[m]) cnt[m]++;
// vis[m] = true;
g[i][m] = true;
}
}
// rep(i, 1, uN) {
// for(int j = 0; j < data[i].size(); j++) {
// if(cnt[data[i][j]] > 1) {
// g[i][data[i][j]] = true;
// }
// }
// }
if(hungary()) puts("YES");
else puts("NO");
}
return 0;
}
D - 棋盘游戏
小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
Input
输入包含多组数据，
第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M)，表示了棋盘的高、宽，以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息：每行两个数X和Y，表示了这个格子在棋盘中的位置。
Output
对输入的每组数据，按照如下格式输出：
Board T have C important blanks for L chessmen.
Sample Input
3 3 4 1 2 1 3 2 1 2 2 3 3 4 1 2 1 3 2 1 3 2
Sample Output
Board 1 have 0 important blanks for 2 chessmen. Board 2 have 3 important blanks for 3 chessmen.
这个建图是把行列拆开，每一行每一列因为只能放一个车所以每行每列看做二分图的一个XY两边，每个匹配表示（x,y）坐标放车。
先建图，然后跑一边匈牙利，然后枚举点删去跑匈牙利，如果删去了影响结果就说明是重要点。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 110;
int lnk[maxn];
bool g[maxn][maxn], used[maxn];
int uN, vN;
bool dfs(int u)
{
for(int v = 1; v <= vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return res;
}
int n, m, k, tmp, ans;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d%d", &n, &m, &k)) {
memset(g, 0, sizeof g);
rep(i, 1, k) {
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = true;
}
uN = vN = n;
tmp = hungary();
ans = 0;
rep(i, 1, n) rep(j, 1, n) if(g[i][j]){
g[i][j] = false;
int t = hungary();
if(t != tmp) ans++;
g[i][j] = true;
}
printf("Board %d have %d important blanks for %d chessmen.\n", Case++, ans, tmp);
}
return 0;
}
E - Swap
Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?
Input
There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.
Output
For each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.
If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.
Sample Input
2 0 1 1 0 2 1 0 1 0
Sample Output
1 R 1 2 -1
根据矩阵性质，这些矩阵肯定是满秩的且能由单一的行列变换得来。然后行列建图跑二分图如果不是完备匹配就说明凉凉。
然后就是考的linker数组的意义，表示X集合元素对应的Y集合元素，操作一波（只行或者只列）用linker数组完成快速变换。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
int n, g[N][N], lnk[N], used[N];
bool dfs(int u)
{
for(int v = 1; v <= n; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= n; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return res;
}
P ans[N];
int l;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d", &n)) {
rep(i, 1, n) rep(j, 1, n) scanf("%d", &g[i][j]);
if(hungary() != n) {
puts("-1");
continue;
}
l = 0;
rep(i, 1, n) {
if(lnk[i] != i) {
int p;
rep(j, i + 1, n) {
if(lnk[j] == i) {
p = j; break;
}
}
swap(lnk[i], lnk[p]);
ans[l].fi = i;
ans[l].se = p;
l++;
}
}
printf("%d\n", l);
rep(i, 0, l - 1) printf("C %d %d\n", ans[i].fi, ans[i].se);
}
return 0;
}
//int n, g[N][N], lnk[N];
//bool flag;
//P ans[N];
//int l;
//
//int main()
//{
// #ifndef ONLINE_JUDGE
// freopen("data.txt", "r", stdin);
// #endif
//
// while(~scanf("%d", &n)) {
// memset(lnk, 0, sizeof lnk);
// flag = true;
// l = 0;
//
// rep(i, 1, n) rep(j, 1, n) {
// scanf("%d", &g[i][j]);
// if(g[i][j]) {
// if(lnk[j]) flag = false;
// else lnk[j] = i;
// }
// }
//
// if(!flag) {
// puts("-1");
// continue;
// }
//
// rep(i, 1, n) {
// if(lnk[i] != i) {
// int p;
// rep(j, i + 1, n) {
// if(lnk[j] == i) {
// p = j; break;
// }
// }
// swap(lnk[i], lnk[p]);
// ans[l].fi = i;
// ans[l].se = p;
// l++;
// }
// }
// printf("%d\n", l);
// rep(i, 0, l - 1) printf("C %d %d\n", ans[i].fi, ans[i].se);
// }
//
// return 0;
//}
F - Rain on your Parade
You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour?
Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however.
Input
The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= s i <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.
Output
For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.
Sample Input
2 1 2 1 0 3 3 0 3 2 4 0 6 0 1 2 1 1 2 3 3 2 2 2 2 4 4
Sample Output
Scenario #1: 2 Scenario #2: 2
首先是建图把每个人和能拿到的伞建边。
然后数据量大要用HK算法，复杂度N^0.5 * E.
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 3010
#define M 3010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int MAXN = 3001;
//const int INF = 0x3f3f3f3f;
vector<int> G[MAXN];
int uN;
int Mx[MAXN], My[MAXN];
int dx[MAXN], dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP() {
queue<int> Q;
dis = INF;
memset(dx, -1, sizeof dx);
memset(dy, -1, sizeof dy);
for(int i = 1; i <= uN; i++) {
if(Mx[i] == -1) {
Q.push(i);
dx[i] = 0;
}
}
while(!Q.empty()) {
int u = Q.front();
Q.pop();
if(dx[u] > dis) break;
int sz = G[u].size();
for(int i = 0; i < sz; i++) {
int v = G[u][i];
if(dy[v] == -1) {
dy[v] = dx[u] + 1;
if(My[v] == -1) dis = dy[v];
else {
dx[My[v]] = dy[v] + 1;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
bool dfs(int u) {
int sz = G[u].size();
for(int i = 0; i < sz; i++) {
int v = G[u][i];
if(!used[v] && dy[v] == dx[u] + 1) {
used[v] = true;
if(My[v] != -1 && dy[v] == dis) continue;
if(My[v] == -1 || dfs(My[v])) {
My[v] = u;
Mx[u] = v;
return true;
}
}
}
return false;
}
int MaxMatch() {
int res = 0;
memset(Mx, -1, sizeof Mx);
memset(My, -1, sizeof My);
while(SearchP()) {
memset(used, false, sizeof used);
for(int i = 1; i <= uN; i++) {
if(Mx[i] == -1 && dfs(i)) res++;
}
}
return res;
}
int t, m, n;
struct ps {
int x, y, s;
}data[M];
P un[M];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &t, &m);
rep(i, 1, m) {
scanf("%d%d%d", &data[i].x, &data[i].y, &data[i].s);
}
scanf("%d", &n);
rep(i, 1, n) scanf("%d%d", &un[i].fi, &un[i].se);
uN = m;
rep(i, 1, uN) G[i].clear();
rep(i, 1, m) rep(j, 1, n) {
double time = sqrt(pow(data[i].x - un[j].fi, 2) + pow(data[i].y - un[j].se, 2)) / data[i].s;
if(time > t) continue;
G[i].push_back(j);
}
printf("Scenario #%d:\n%d\n\n", Case++, MaxMatch());
}
return 0;
}
G - Oil Skimming
Thanks to a certain "green" resources company, there is a new profitable industry of oil skimming. There are large slicks of crude oil floating in the Gulf of Mexico just waiting to be scooped up by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water collecting oil on the water's surface. However, each scoop covers a 10m by 20m rectangle (going either east/west or north/south). It also requires that the rectangle be completely covered in oil, otherwise the product is contaminated by pure ocean water and thus unprofitable! Given a map of an oil slick, the oil baron would like you to compute the maximum number of scoops that may be extracted. The map is an NxN grid where each cell represents a 10m square of water, and each cell is marked as either being covered in oil or pure water.
Input
The input starts with an integer K (1 <= K <= 100) indicating the number of cases. Each case starts with an integer N (1 <= N <= 600) indicating the size of the square grid. Each of the following N lines contains N characters that represent the cells of a row in the grid. A character of '#' represents an oily cell, and a character of '.' represents a pure water cell.
Output
For each case, one line should be produced, formatted exactly as follows: "Case X: M" where X is the case number (starting from 1) and M is the maximum number of scoops of oil that may be extracted.
Sample Input
1 6 ...... .##... .##... ....#. ....## ......
Sample Output
Case 1: 3
用1x2的矩阵来覆盖#，
奇偶性建图，把下标和为奇数和偶数的分为XY，建边，跑匈牙利。
昂直接用了上题的HK了，匈牙利就行其实。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 610
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int MAXN = 601 * 601;
//const int INF = 0x3f3f3f3f;
vector<int> G[MAXN];
int uN;
int Mx[MAXN], My[MAXN];
int dx[MAXN], dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP() {
queue<int> Q;
dis = INF;
memset(dx, -1, sizeof dx);
memset(dy, -1, sizeof dy);
for(int i = 0; i < uN; i++) {
if(Mx[i] == -1) {
Q.push(i);
dx[i] = 0;
}
}
while(!Q.empty()) {
int u = Q.front();
Q.pop();
if(dx[u] > dis) break;
int sz = G[u].size();
for(int i = 0; i < sz; i++) {
int v = G[u][i];
if(dy[v] == -1) {
dy[v] = dx[u] + 1;
if(My[v] == -1) dis = dy[v];
else {
dx[My[v]] = dy[v] + 1;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
bool dfs(int u) {
int sz = G[u].size();
for(int i = 0; i < sz; i++) {
int v = G[u][i];
if(!used[v] && dy[v] == dx[u] + 1) {
used[v] = true;
if(My[v] != -1 && dy[v] == dis) continue;
if(My[v] == -1 || dfs(My[v])) {
My[v] = u;
Mx[u] = v;
return true;
}
}
}
return false;
}
int MaxMatch() {
int res = 0;
memset(Mx, -1, sizeof Mx);
memset(My, -1, sizeof My);
while(SearchP()) {
memset(used, false, sizeof used);
for(int i = 0; i < uN; i++) {
if(Mx[i] == -1 && dfs(i)) res++;
}
}
return res;
}
char s[N][N];
int Dx[] = {0, 0, 1, -1};
int Dy[] = {1, -1, 0, 0};
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
rep(i, 0, n - 1) scanf("%s", s[i]);
uN = n * n;
rep(i, 0, n - 1) rep(j, 0, n - 1) if(((i + j) & 1) && s[i][j] == '#') {
rep(k, 0, 3) {
int x = Dx[k] + i, y = Dy[k] + j;
if(x < 0 || x >= n || y < 0 || y >= n) continue;
if(s[x][y] != '#') continue;
G[i * n + j].push_back(x * n + y);
}
}
printf("Case %d: %d\n", Case++, MaxMatch());
rep(i, 0, uN - 1) G[i].clear();
}
return 0;
}
H - Antenna Placement
The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.
Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?
Input
On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1 <= h <= 40 and 0 < w <= 10. Thereafter is a matrix presented, describing the points of interest in Sweden in the form of h lines, each containing w characters from the set ['*','o']. A '*'-character symbolises a point of interest, whereas a 'o'-character represents open space.
Output
For each scenario, output the minimum number of antennas necessary to cover all '*'-entries in the scenario's matrix, on a row of its own.
Sample Input
2 7 9 ooo**oooo **oo*ooo* o*oo**o** ooooooooo *******oo o*o*oo*oo *******oo 10 1 * * * o * * * * * *
Sample Output
17 5
二分图的最小边覆盖数=图中的顶点数-（最小点覆盖数）该二分图的最大匹配数
建图是左边右边都是所有点。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
bool g[N * N][N * N], used[N * N];
int lnk[N * N], uN, vN;
bool dfs(int u)
{
for(int v = 0; v < vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 0; u < uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return uN - res / 2;
}
char s[N][N];
int n, m;
int Dx[] = {0, 0, 1, -1};
int Dy[] = {1, -1, 0, 0};
map<int, int> mp;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
rep(i, 0, n - 1) scanf("%s", s[i]);
memset(g, 0, sizeof g);
mp.clear();
uN = 0;
rep(i, 0, n - 1) rep(j, 0, m - 1) if(s[i][j] == '*') {
mp[i*m+j] = uN; uN++;
}
rep(i, 0, n - 1) rep(j, 0, m - 1) if(s[i][j] == '*') {
rep(k, 0, 3) {
int x = i + Dx[k], y = j + Dy[k];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(s[x][y] != '*') continue;
g[mp[i*m+j]][mp[x*m+y]] = true;
}
}
vN = uN;
printf("%d\n", hungary());
}
return 0;
}
//
//const int MAXN = 601 * 601;
////const int INF = 0x3f3f3f3f;
//vector<int> G[MAXN];
//int uN;
//int Mx[MAXN], My[MAXN];
//int dx[MAXN], dy[MAXN];
//int dis;
//bool used[MAXN];
//bool SearchP() {
// queue<int> Q;
// dis = INF;
// memset(dx, -1, sizeof dx);
// memset(dy, -1, sizeof dy);
// for(int i = 0; i < uN; i++) {
// if(Mx[i] == -1) {
// Q.push(i);
// dx[i] = 0;
// }
// }
// while(!Q.empty()) {
// int u = Q.front();
// Q.pop();
// if(dx[u] > dis) break;
// int sz = G[u].size();
// for(int i = 0; i < sz; i++) {
// int v = G[u][i];
// if(dy[v] == -1) {
// dy[v] = dx[u] + 1;
// if(My[v] == -1) dis = dy[v];
// else {
// dx[My[v]] = dy[v] + 1;
// Q.push(My[v]);
// }
// }
// }
// }
// return dis != INF;
//}
//bool dfs(int u) {
// int sz = G[u].size();
// for(int i = 0; i < sz; i++) {
// int v = G[u][i];
// if(!used[v] && dy[v] == dx[u] + 1) {
// used[v] = true;
// if(My[v] != -1 && dy[v] == dis) continue;
// if(My[v] == -1 || dfs(My[v])) {
// My[v] = u;
// Mx[u] = v;
// return true;
// }
// }
// }
// return false;
//}
//int MaxMatch() {
// int res = 0;
// memset(Mx, -1, sizeof Mx);
// memset(My, -1, sizeof My);
// while(SearchP()) {
// memset(used, false, sizeof used);
// for(int i = 0; i < uN; i++) {
// if(Mx[i] == -1 && dfs(i)) res++;
// }
// }
// return res;
//}
//
//
//char s[N][N];
//int Dx[] = {0, 0, 1, -1};
//int Dy[] = {1, -1, 0, 0};
//int n, m;
//
//int getcode(int i, int j, int x, int y, int k)
//{
// if(k == 0) return i * (m - 1 + m) + j;
// if(k == 1) return i * (m - 1 + m) + y;
// if(k == 2) return i * (m - 1 + m) + m - 1 + j;
// if(k == 3) return x * (m - 1 + m) + m - 1 + j;
//}
//set<ll> st;
//
//int main()
//{
// #ifndef ONLINE_JUDGE
// freopen("data.txt", "r", stdin);
// #endif
//
// int t;
// scanf("%d", &t);
//
// while(t--) {
// scanf("%d%d", &n, &m);
// rep(i, 0, n - 1) scanf("%s", s[i]);
////rep(i, 0, n - 1) cout <<s[i] << endl;
// uN = n * m;
// st.clear();
// rep(i, 0, n - 1) rep(j, 0, m - 1) if(((i + j) & 1) && s[i][j] == '*'){//cout << i <<' '<<j<<endl;
// rep(k, 0, 3) {
// int x = i + Dx[k], y = j + Dy[k];
// // cout <<"x " << x << ' '<< y <<' '<<s[x][y]<< endl;
// if(x < 0 || x >= n || y < 0 || y >= m) continue;
// if(s[x][y] != '*') continue;
//
// int cd = getcode(i, j, x, y, k);
// if(st.find((ll)(i*m+j)*100000+cd) == st.end()) G[i*m+j].push_back(cd), st.insert((ll)(i*m+j)*100000+cd);
// if(st.find((ll)(x*m+y)*100000+cd) == st.end()) G[x*m+y].push_back(cd), st.insert((ll)(x*m+y)*100000+cd);
// // cout << i << ' ' << j<<' '<<x<<' '<<y<<' ' <<cd<<endl;
// }
// }
//set<ll>::iterator it;
//for(it = st.begin(); it != st.end(); ++it)
// cout <<*it << endl;
// printf("%d %d\n", uN, MaxMatch());
// rep(i, 0, uN - 1) G[i].clear();
// }
//
// return 0;
//}
I - Strategic Game
Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?
Your program should find the minimum number of soldiers that Bob has to put for a given tree.
The input file contains several data sets in text format. Each data set represents a tree with the following description:
the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)
The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.
For example for the tree:
the solution is one soldier ( at the node 1).
The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:
Input
4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)
Output
1 2
Sample Input
4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)
Sample Output
1 2
最小点覆盖=最大匹配
建图双向。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int MAXN = 1510;
const int MAXM = 3010;
struct Edge {
int to, nxt;
}edge[MAXM];
int head[MAXN], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v)
{
edge[tot].to = v; edge[tot].nxt = head[u];
head[u] = tot++;
}
int lnk[MAXN];
bool used[MAXN];
int uN;
bool dfs(int u)
{
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(!used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int i = 0; i < uN; i++) {
memset(used, 0, sizeof used);
if(dfs(i)) res++;
}
return res / 2;
}
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d", &n)) {
init();
uN = n;
rep(i, 0, n - 1) {
int u, tmp, v;
scanf("%d:(%d)", &u, &tmp);
while(tmp--) {
scanf("%d", &v);
addedge(u, v);
addedge(v, u);
}
}
printf("%d\n", hungary());
}
return 0;
}
J - Air Raid
Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.
With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.
Input
Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:
no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets
The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.
There are no blank lines between consecutive sets of data. Input data are correct.
Output
The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.
Sample Input
2 4 3 3 4 1 3 2 3 3 3 1 3 1 2 2 3
Sample Output
2 1
DAG最小不相交路径覆盖。
把原图的每个点V拆成Vx和Vy两个点，如果有一条有向边A->B，那么就加边Ax−>ByAx−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int MAXN = 151;
const int MAXM = 30100;
struct Edge {
int to, nxt;
}edge[MAXM];
int head[MAXN], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v)
{
edge[tot].to = v; edge[tot].nxt = head[u];
head[u] = tot++;
}
int lnk[MAXN];
bool used[MAXN];
int uN;
bool dfs(int u)
{
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(!used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int i = 1; i <= uN; i++) {
memset(used, 0, sizeof used);
if(dfs(i)) res++;
}
return res;
}
int n, m;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
init();
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
}
uN = n;
printf("%d\n", n - hungary());
}
return 0;
}
K - Treasure Exploration
Have you ever read any book about treasure exploration? Have you ever see any film about treasure exploration? Have you ever explored treasure? If you never have such experiences, you would never know what fun treasure exploring brings to you.
Recently, a company named EUC (Exploring the Unknown Company) plan to explore an unknown place on Mars, which is considered full of treasure. For fast development of technology and bad environment for human beings, EUC sends some robots to explore the treasure.
To make it easy, we use a graph, which is formed by N points (these N points are numbered from 1 to N), to represent the places to be explored. And some points are connected by one-way road, which means that, through the road, a robot can only move from one end to the other end, but cannot move back. For some unknown reasons, there is no circle in this graph. The robots can be sent to any point from Earth by rockets. After landing, the robot can visit some points through the roads, and it can choose some points, which are on its roads, to explore. You should notice that the roads of two different robots may contain some same point.
For financial reason, EUC wants to use minimal number of robots to explore all the points on Mars.
As an ICPCer, who has excellent programming skill, can your help EUC?
Input
The input will consist of several test cases. For each test case, two integers N (1 <= N <= 500) and M (0 <= M <= 5000) are given in the first line, indicating the number of points and the number of one-way roads in the graph respectively. Each of the following M lines contains two different integers A and B, indicating there is a one-way from A to B (0 < A, B <= N). The input is terminated by a single line with two zeros.
Output
For each test of the input, print a line containing the least robots needed.
Sample Input
1 0 2 1 1 2 2 0 0 0
Sample Output
1 1 2
DAG最小相交路径覆盖
floyed求闭包，然后就可以看成不相交的覆盖。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 510;
bool g[maxn][maxn];
int lnk[maxn];
int uN, vN;
bool used[maxn];
bool dfs(int u)
{
for(int v = 1; v <= vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return res;
}
int n, m;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d", &n, &m) && n + m) {
memset(g, 0, sizeof g);
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
g[u][v] = true;
}
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) {
if(g[i][k] && g[k][j]) g[i][j] = true;
}
uN = vN = n;
printf("%d\n", n - hungary());
}
return 0;
}
L - Cat VS Dog
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.
这题有点难看出是二分图，难在建图。
最大独立集。二分图的最大点独立数=点的个数-最小点覆盖数（最大匹配）
因为是求人开不开心，所以对人建图，猫狗用来判断人和人有没有冲突，冲突就建边（XY等价）。
所以问题变成在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。
也就似乎最大独立集。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 50
#define M 20010
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-5;
const double PI = acos(-1);
int Case = 1;
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)
const int maxn = 510;
bool g[maxn][maxn];
int lnk[maxn];
int uN, vN;
bool used[maxn];
bool dfs(int u)
{
for(int v = 1; v <= vN; v++) {
if(g[u][v] && !used[v]) {
used[v] = true;
if(lnk[v] == -1 || dfs(lnk[v])) {
lnk[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(lnk, -1, sizeof lnk);
for(int u = 1; u <= uN; u++) {
memset(used, false, sizeof used);
if(dfs(u)) res++;
}
return res / 2;
}
int n, m, p;
char ch1, ch2;
int a[maxn], b[maxn];
bool c[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d%d", &n, &m, &p)) {
memset(g, 0, sizeof g);
memset(c, 0, sizeof c);
rep(i, 1, p) {
cin >> ch1 >> a[i] >> ch2 >> b[i];
if(ch1 == 'C') c[i] = true;
}
uN = vN = p;
rep(i, 1, p) rep(j, 1, p) {
if(c[i] != c[j] && (a[i] == b[j] || b[i] == a[j])) {
g[i][j] = g[j][i] = true;//cout << i << ' ' << j << endl;
}
}
printf("%d\n", p - hungary());
}
return 0;
}
M - Jamie's Contact Groups
Jamie is a very popular girl and has quite a lot of friends, so she always keeps a very long contact list in her cell phone. The contact list has become so long that it often takes a long time for her to browse through the whole list to find a friend's number. As Jamie's best friend and a programming genius, you suggest that she group the contact list and minimize the size of the largest group, so that it will be easier for her to search for a friend's number among the groups. Jamie takes your advice and gives you her entire contact list containing her friends' names, the number of groups she wishes to have and what groups every friend could belong to. Your task is to write a program that takes the list and organizes it into groups such that each friend appears in only one of those groups and the size of the largest group is minimized.
Input
There will be at most 20 test cases. Ease case starts with a line containing two integers N and M. where N is the length of the contact list and M is the number of groups. N lines then follow. Each line contains a friend's name and the groups the friend could belong to. You can assume N is no more than 1000 and M is no more than 500. The names will contain alphabet letters only and will be no longer than 15 characters. No two friends have the same name. The group label is an integer between 0 and M - 1. After the last test case, there is a single line `0 0' that terminates the input.
Output
For each test case, output a line containing a single integer, the size of the largest contact group.
Sample Input
3 2 John 0 1 Rose 1 Mary 1 5 4 ACM 1 2 3 ICPC 0 1 Asian 0 2 3 Regional 1 2 ShangHai 0 2 0 0
Sample Output
2 2
二分图多重匹配。
跑网络流就行了。。。
好像有专门的多重匹配板子，大概不需要了。
还有人 是让Y集里的点能匹配多次的写法跑匈牙利。
二分下。
#include <cstdio>#include <cstring>#include <utility>#include <iostream>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <string>#include <vector>using namespace std;typedef pair<int, int> P;typedef long long ll;#define N 50#define M 20010const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-5;const double PI = acos(-1);int Case = 1;#define fi first#define se second#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)#define rrep(i, lll, nnn) for(int i = (lll); i >= (nnn); i--)const int MAXN = 2010;const int MAXM = 1000010;struct Node{ int from,to,next; int cap;}edge[MAXM], newedge[MAXM];int tol;int dep[MAXN];//dep为点的层次int head[MAXN];int newhead[MAXN];int stack[MAXN];//stack为栈，存储当前增广路int cur[MAXN];//存储当前点的后继void init(){ tol=0; memset(head,-1,sizeof(head));}void addedge(int u,int v,int w)//第一条变下标必须为偶数{ edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++;}int BFS(int start,int end){ int que[MAXN]; int front,rear; front=rear=0; memset(dep,-1,sizeof(dep)); que[rear++]=start; dep[start]=0; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; if(rear>=MAXN)rear=0; if(v==end)return 1; } } } return 0;}int dinic(int start,int end){ int res=0; int top; while(BFS(start,end)) { memcpy(cur,head,sizeof(head)); int u=start; top=0; while(1) { if(u==end) { int min=INF; int loc; for(int i=0;i<top;i++) if(min>edge[stack[i]].cap) { min=edge[stack[i]].cap; loc=i; } for(int i=0;i<top;i++) { edge[stack[i]].cap-=min; edge[stack[i]^1].cap+=min; } res+=min; top=loc; u=edge[stack[top]].from; } for(int i=cur[u];i!=-1;cur[u]=i=edge[i].next) if(edge[i].cap!=0&&dep[u]+1==dep[edge[i].to]) break; if(cur[u]!=-1) { stack[top++]=cur[u]; u=edge[cur[u]].to; } else { if(top==0)break; dep[u]=-1; u=edge[stack[--top]].from; } } } return res;}int n, m, ans;char s[10000];bool check(int mid){ memcpy(head, newhead,