2014
02-27

# Chinese Chess

Winnie is very interested in chinese chess. Now, let’s consider a game which is similar to it. There is a N * M chess board, we hope we can put rooks as more as possible. But just a certain number of postions can be put rooks on. One rook can attack another if they are in the same row or column. Now you may think this is a very simple problem for you. But as very whuacmers know, winnie is evil enough to cheat you. Let’s consider some positions called critical postions. If we don’t put rook on the critical position, the maximum number of rook we can put on this chess board will reduce. How many critical positions on the chess board?

Input will contain multiple test cases. The first line contains three numbers N, M, K(N, M ≤ 10000, K ≤ 100000) which indicate height, width and number of positions which can be put rook on. Then next K lines follow, each contains two integer X ans Y which indicate we can put rook on the Xth row, Yth column.

Input will contain multiple test cases. The first line contains three numbers N, M, K(N, M ≤ 10000, K ≤ 100000) which indicate height, width and number of positions which can be put rook on. Then next K lines follow, each contains two integer X ans Y which indicate we can put rook on the Xth row, Yth column.

3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2 

Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.

Hint
Hint: huge input, use scanf please.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

const int maxn = 100000;
const int maxm = 1010*1010;

const int INF = 0x3f3f3f3f;

int nx, ny;
int n, m, k;
int cnt;

struct Edge
{
int u, v;
int next;
}edge[maxm];

int first[maxn];

bool vis[maxn];

bool edges[maxn];

void init()
{
cnt = 0;
memset(first, -1, sizeof(first));
memset(edges, 0, sizeof(edges));
}

{
edge[cnt].u = u, edge[cnt].v = v;
edge[cnt].next = first[u], first[u] = cnt++;
}

int dis;

int dx[maxn], dy[maxn];

int bfs()
{
queue<int> q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for(int i = 1; i <= nx; i++)
{
{
q.push(i);
dx[i] = 0;
}
}
while(!q.empty())
{
int u = q.front(); q.pop();
if(dx[u] > dis) break;
for(int e = first[u]; e != -1; e = edge[e].next)
{
if(edges[e]) continue;
int v = edge[e].v;
if(dy[v] == -1)
{
dy[v] = dx[u] + 1;
if(ylink[v] == -1) dis = dy[v];
else
{
}
}
}
}
return dis != INF;
}

int find(int u)
{
int v;
for(int e = first[u]; e != -1; e = edge[e].next)
{
if(edges[e]) continue;
v = edge[e].v;
if(!vis[v] && dy[v] == dx[u]+1)
{
vis[v] = 1;
if(ylink[v] != -1 && dy[v] == dis) continue;
{
return 1;
}
}
}
return 0;
}

int MaxMatch()
{
int ans = 0;
while(bfs())
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= nx; i++) if(xlink[i] == -1)
{
ans += find(i);
}
}
return ans;
}

{
char c = getchar();
while(!isdigit(c)) c = getchar();

x = 0;
while(isdigit(c))
{
x = x*10 + c-'0';
c = getchar();
}
}

inline void writeint(int x)
{
if(x > 9) writeint(x/10);
putchar(x%10+'0');
}

{
init();
while(k--)
{
int u, v;
}
}

int times;

int find_edge(int u, int v)
{
for(int e = first[u]; e != -1; e = edge[e].next)
{
if(edge[e].v == v) return e;
}
return -1;
}

void solve()
{
int ans = MaxMatch();
int count = 0;

for(int u = 1; u <= nx; u++)
{
{
edges[e] = 1;
int t = MaxMatch();
if(t != ans) count++;
edges[e] = 0;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", ++times, count, ans);
}

int main()
{
times = 0;
while(~scanf("%d%d%d", &nx, &ny, &k))
{
solve();
}
return 0;
}