bzoj1143:[ctsc2008]祭祀river

关键词：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<bitset>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define qwq(x) for(edge *o=head[x];o;o=o->next)
int read(){
    int x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
    return x;
}
const int nmax=105;
const int maxn=10005;
const int inf=0x7f7f7f7f;
struct edge{
    int to;edge *next;
};
edge es[maxn],*pt=es,*head[nmax];
void add(int u,int v){
    pt->to=v;pt->next=head[u];head[u]=pt++;
}
bitset<nmax>vis;
int match[nmax],dis[nmax][nmax];
bool dfs(int x){
    qwq(x) if(!vis[o->to]) {
        vis[o->to]=1;
        if(!match[o->to]||dfs(match[o->to])) {
            match[o->to]=x;return true;
        }
    }
    return false;
}
int main(){
    int n=read(),m=read(),u,v;
    rep(i,1,m) u=read(),v=read(),dis[u][v]=1;
    rep(i,1,n) rep(j,1,n) rep(k,1,n) dis[j][k]|=(dis[j][i]&dis[i][k]);
    rep(i,1,n) rep(j,1,n) if(i!=j&&dis[i][j]) add(i,j);
    int ans=n;
    rep(i,1,n) {
        vis.reset();
        if(dfs(i)) ans--;
    }
    printf("%d
",ans);
    return 0;
}

bzoj1143:[ctsc2008]祭祀river

...龙王为神。每逢重大庆典，Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（... 查看详情

bzoj1143:[ctsc2008]祭祀river

二分图的最大独立集可以符合就是最少用多少个点就能够覆盖所有的边那么其他的点选的话就没有矛盾的了。符合题意、//反思：有向图根本没有联想到二分图，想的一直是暴力暴力暴力。。。以为数据那么小。。。应该联想有... 查看详情

bzoj1143:[ctsc2008]祭祀river

【题意】求DAG上最多的点使得互不可达。【算法】floyd+最大匹配【题解】链是DAG上的一个点集，集合内的点相互单向可达。反链是DAG上的一个点集，集合内的点相互不可达。题目显然是求最长反链，转化为最小链覆盖。最小链覆... 查看详情

[bzoj]1143:[ctsc2008]祭祀river

题目大意：给定一个n个点m条边的有向无环图，问最多选多少个点使得两两之间互不到达。（n<=100，m<=1000）思路：题目所求即最长反链，最长反链=最小链覆盖，对每个点向自己能到的点连边后，转化成最小路径覆盖，每个... 查看详情

bzoj1143:[ctsc2008]祭祀river最长反链(代码片段)

...龙王为神。每逢重大庆典，Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（... 查看详情

[bzoj1143][ctsc2008]祭祀river

题面戳我sol介绍几个基于有向无环图（DAG）的概念：链广义上来说，链是一个点集，其中任意两点u，v，都满足[u能到达v]+[v能到达u]=1（就是说两个只满足其一）反链与链的定义类似，就是任意两个点都无法到达。这个题要求的... 查看详情

$bzoj1143-ctsc2008$祭祀$river$最小链覆盖-最大反链(代码片段)

...王为神。每逢重大庆典，\(Y\)族都会在水面上举办盛大的祭祀活动。我们可以把\(Y\)族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环... 查看详情

bzoj.1143.[ctsc2008]祭祀(最长反链最大流isap)

题目链接题目是求最长反链，反链指点集内任意两点不能互相到达。根据Dilworth定理，在DAG中，\[最长反链=最小路径覆盖=V-最大匹配数\]用Floyd求一遍传递闭包后，在所有可互相到达的点间连边。求二分图最大匹配。也可以这么理... 查看详情

1143:[ctsc2008]祭祀river(代码片段)

...龙王为神。每逢重大庆典，Y族都会在水面上举办盛大的祭祀 查看详情

1143:[ctsc2008]祭祀river（最长反链）(代码片段)

1143:[CTSC2008]祭祀river题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1143Description:　　在遥远的东方，有一个神秘的民族，自称Y族。他们世代居住在水面上，奉龙王为神。每逢重大庆典，Y族都会在水面上举办盛大的祭祀活动。我... 查看详情

[1143][ctsc2008]祭祀river（最大独立集||偏序集最大反链）

传送门 网上说这是偏序集最大反链，然而我实在不理解。所以我换了一个思路，先用floyed，根据点的连通性连边，问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立集。 ——代码1#include<... 查看详情

[ctsc2008]祭祀(代码片段)

[题目链接]     https://www.lydsy.com/JudgeOnline/problem.php?id=1143[算法]     答案为最小路径可重复点覆盖所包含的路径数，将原图G进行弗洛伊德传递闭包，得到一张新图G‘，然后求出拆点二分图G2‘... 查看详情

[bzoj1143]祭祀

这题水很深...题目给了一个有向无环图，要求找出最多的点且这些点中不存在两个点使得它们之间有路径如果$x$能到$y$，那么$x,y$只能选其中一个，所以连上一条边$(x,y)$不改变答案（其实是在找传递闭包）这时可以转化一下题目... 查看详情

[ctsc2008]祭祀river(代码片段)

...龙王为神。每逢重大庆典，Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（... 查看详情

洛谷p2774方格取数问题bzoj1143祭祀river二分图最大独立集(代码片段)

讲解前首先引入两个概念二分图最小点覆盖集定义：在二分图中求出一个最小点集使得图中任意一条边至少有一个端点在点集内解法：对二分图进行最大匹配最大匹配数就是二分图的最小点覆盖集包含的点数***************************... 查看详情

bzoj1146ctsc2008网络管理[整体二分]

网络管理TimeLimit: 50Sec  MemoryLimit: 162MB[Submit][Status][Discuss]Description　　M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。　　为了让分布在世界各地的N个部门之间协同工作，公司搭建... 查看详情

bzoj3555:[ctsc2014]企鹅qq

二次联通门: BZOJ3555:[Ctsc2014]企鹅QQ     /*BZOJ3555:[Ctsc2014]企鹅QQ哈希先处理出所有串的哈希值后枚举每一位，删去该位排序统计相同的个数即可*/#include<algorithm>#include<cstring>#include<cstdio>voi 查看详情

bzoj1143(代码片段)

求最长反链裸题 补充一点知识。。 　　链         :  D中的一个子集C 满足C是全序集 及C中所有元素都可以比较大小    反链       查看详情