首页 > ACM题库 > HDU-杭电 > HDU 3026- Chinese Chess-分治-[解题报告]HOJ
2014
02-27

HDU 3026- Chinese Chess-分治-[解题报告]HOJ

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];

int xlink[maxn], ylink[maxn];
bool vis[maxn];

bool edges[maxn];

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

void read_graph(int u, int v)
{
	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++)
    {
        if(xlink[i] == -1)
        {
            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
                {
                    dx[ylink[v]] = dy[v]+1;
                    q.push(ylink[v]);
                }
            }
        }
    }
    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;
            if(ylink[v] == -1 || find(ylink[v]))
            {
                xlink[u] = v, ylink[v] = u;
                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;
}

inline void readint(int &x)
{
	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');
}

void read_case()
{
    init();
    while(k--)
    {
        int u, v;
        readint(u), readint(v);
        read_graph(u, v);
    }
}

int XLINK[maxn];

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()
{
    read_case();
    int ans = MaxMatch();
    int count = 0;
    memcpy(XLINK, xlink, sizeof(xlink));
    
    for(int u = 1; u <= nx; u++)
    {
        memset(xlink, -1, sizeof(xlink));
        memset(ylink, -1, sizeof(ylink));
        if(XLINK[u] != -1)
        {
			int e = find_edge(u, XLINK[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;
}


参考:http://blog.csdn.net/wall_f/article/details/8988714