BZOJ 2718: [Violet 4]毕业旅行( 最长反链 )

一不小心速度就成了#1....

这道题显然是求最长反链, 最长反链=最小链覆盖.最小链覆盖就是先做一次floyd传递闭包, 再求最小路径覆盖. 最小路径覆盖=N - 二分图最大匹配. 所以把所有点拆成x,y两个, 然后存在edge(u,v)就连u_x->v_y. 然后跑匈牙利即可.

------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

const int maxn = 209;

inline int read() {

char c = getchar();

int ret = 0;

for(; !isdigit(c); c = getchar());

for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0';

return ret;

}

struct edge {

int to;

edge* next;

} E[maxn * maxn], *pt = E, *head[maxn];

inline void addedge(int u, int v) {

pt->to = v; pt->next = head[u]; head[u] = pt++;

}

bitset<maxn> d[maxn];

int vis[maxn], match[maxn], N, C;

bool dfs(int x) {

for(edge* e = head[x]; e; e = e->next) if(vis[e->to] != C) {

vis[e->to] = C;

if(!~match[e->to] || dfs(match[e->to])) {

match[e->to] = x;

return true;

}

return false;

}

int main() {

memset(match, -1, sizeof match);

memset(vis, -1, sizeof vis);

N = read();

int m = read();

for(int i = 0; i < N; i++) d[i].reset();

while(m--) d[read() - 1][read() - 1] = 1;

for(int i = 0; i < N; i++)

for(int j = 0; j < N; j++)

if(d[j][i]) d[j] |= d[i];

for(int i = 0; i < N; i++)

for(int j = 0; j < N; j++)

if(d[i][j]) addedge(i, j);

int ans = N;

for(C = 0; C < N; C++) if(dfs(C)) ans--;

printf("%d\n", ans);

return 0;

}

------------------------------------------------------------------

2718: [Violet 4]毕业旅行

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 317 Solved: 178
[Submit][Status][Discuss]

Description

Input

Output

最多可选多少景点

Sample Input

7 6
1 2
2 3
5 4
4 3
3 6
6 7

Sample Output

HINT

Source

Ctsc2008 River & ural 1533. Fat Hobbits

巴特西