BZOJ1143: [CTSC2008]祭祀river
二分图 floyd 传递闭包    2016-11-02 19:03:38    223    -1    0

1143: [CTSC2008]祭祀river

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2259  Solved: 1140
[Submit][Status][Discuss]

Description

  在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都
会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着
两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。

 

  由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必
须非常慎重。准确地说,Y族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失去它神圣
的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。

Input

  第一行包含两个用空格隔开的整数N、M,分别表示岔口和河道的数目,岔口从1到N编号。接下来M行,每行包

 

含两个用空格隔开的整数u、v,描述一条连接岔口u和岔口v的河道,水流方向为自u向v。 N ≤ 100 M ≤ 1 000

Output

  第一行包含一个整数K,表示最多能选取的祭祀点的个数。

Sample Input

4 4
1 2
3 4
3 2
4 2

Sample Output

2

【样例说明】
在样例给出的水系中,不存在一种方法能够选择三个或者三个以上的祭祀点。包含两个祭祀点的测试点的方案有两种:
选择岔口1与岔口3(如样例输出第二行),选择岔口1与岔口4。
水流可以从任意岔口流至岔口2。如果在岔口2建立祭祀点,那么任意其他岔口都不能建立祭祀点
但是在最优的一种祭祀点的选取方案中我们可以建立两个祭祀点,所以岔口2不能建立祭祀点。对于其他岔口
至少存在一个最优方案选择该岔口为祭祀点,所以输出为1011。
 

Solution

最长反链长度=最少链覆盖数

然后就变成了求最少链覆盖数

我们先看路径不能相交的最小路径覆盖怎么来做:

 

建立一个二分图,两边都是n个点,原图的每个点 i 对应两个,在左边的叫做 i1, 在右边的叫做 i2 

然后原图中如果存在一条边 (x, y),那么就在二分图中建立 (x1, y2) 的边

这样建立二分图之后,原图的点数 n - 二分图最大匹配 = 原图的最小路径覆盖(路径不能相交)

这样为什么是对的呢?我们可以认为,开始时原图的每个点都是独立的一条路径,然后我们每次在二分图中选出一条边,就是将两条路径连接成一条路径,答案数就减少1

而路径是不能相交的,所以我们在二分图中选出的边也是不能相交的,所以就是二分图的最大匹配

了解了路径不能相交的最小路径覆盖之后,怎么解路径可以相交的最小路径覆盖(也就是最小链覆盖)呢?

我们将原图做一次Floyd传递闭包,之后就可以知道任意两点 x, y,x 是否能到达 y

如果两个点 x, y,满足 x 可以到达 y ,那么就在二分图中建立边 (x1, y2) 

这样其实就是相当于将原图改造了一下,只要 x 能到达 y ,就直接连一条边 (x, y),这样就可以“绕过”原图的一些被其他路径占用的点,直接构造新路径了

这样就将可以相交的最小路径覆盖转化为了路径不能相交的最小路径覆盖了

 

Source code

/*{{{*/
#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

typedef std::pair<int, int> pii;

std::string program_name = __FILE__;
std::string iput = program_name.substr(0, program_name.length() - 4) + ".in";
std::string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
template <class T> void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top) 
        putchar(s[top --]);
    putchar(p);
}
/*}}}*/
 
const int maxn = 100 + 5;
 
int n;
int m;
int a[maxn];
bool to[maxn][maxn];

int st[maxn], cnte;
struct edge { int to, next; } e[maxn * maxn];

inline void addedge(int u, int v)
{
    e[++ cnte] = (edge) {v, st[u]};
    st[u] = cnte;
}

int Time;
int vis[maxn * 2];
int fa[maxn * 2];

bool find(int x)
{
    for (int i = st[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (vis[v] == Time) continue;
        vis[v] = Time;
        if (fa[v] == 0 || find(fa[v])) {
            fa[v] = x;
            return true;
        }
    }
    return false;
}


void exec() 
{
    read(n);
    read(m);
    for (int i = 1; i <= m; ++ i) {
        int u, v;
        read(u); read(v);
        to[u][v] = 1;
    }

    for (int k = 1; k <= n; ++ k)
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j)
                to[i][j] |= to[i][k] && to[k][j];

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (to[i][j])
                addedge(i, n + j);

    int ans = n;
    for (Time = 1; Time <= n; ++ Time) {
        ans -= find(Time);
    }
    write(ans);
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r") != NULL) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }

    do exec();
    while (0);

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/


 

NOIP2016与赛前日记
223 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航