首页 > 其他分享 >P6121 [USACO16OPEN] Closing the Farm G

P6121 [USACO16OPEN] Closing the Farm G

时间:2024-03-08 14:33:59浏览次数:30  
标签:P6121 Farm ll fa Closing now open finds 200005

原题链接

题解

抽象化
抽象成点和边,对于抹除一个点,判断整个图是否联通
等价于建立一个点(被抹除点的前一个点),判断这个点与周围点相连后,累积合并次数是否等于点数减一

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
ll fa[200005];
ll finds(ll now){return (fa[now]=(now==fa[now])?now:finds(fa[now]));}
ll ans[200005]={0};
ll open[200005]={0},bing=0,shut[200005]={0};
vector<ll> G[200005];
inline void read(ll &x) {
	x = 0;
	ll flag = 1;
	char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
	while(c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
    	putchar('-');
		x = -x;
	}
    if(x > 9)
		write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    ll n,m;
    read(n);read(m);
    for(ll i=1;i<=n;i++)fa[i]=i;
    for(ll i=1;i<=m;i++)
    {
        ll x,y;
        read(x);read(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(ll i=1;i<=n;i++) read(shut[i]);
    for(ll i=n;i>=1;i--)
    {
        ll x=shut[i];
        open[x]=1;
        for(auto to:G[x]) if(open[to]&&finds(to)!=x&&(++bing)) fa[finds(to)]=x;
        ans[i]=(bing==n-i?1:0);
    }
    for(ll i=1;i<=n;i++) puts((ans[i]==1)?"YES":"NO");
    return 0;
}

标签:P6121,Farm,ll,fa,Closing,now,open,finds,200005
From: https://www.cnblogs.com/pure4knowledge/p/18060898

相关文章

  • [USACO13MAR]Farm Painting S 题解
    看大家好多写的都用了四维偏序,给一个不用偏序的解法。简化一下题目,就是给你\(n\)个矩形,第\(i\)个矩形用\((x1_i,y1_i,x2_i,y2_i)\)表示,问你有多少个\(i\)满足:不存在另一个\(j\)使得\(x1_j\lex1_i\lex2_j\wedgey1_j\ley1_i\ley2_j\)。我们从左到右扫描每一个......
  • Go 100 mistakes - #79: Not closing transient resources
        ......
  • Bzoj3829. FarmCraft
     Descriptionmhy住在一棵有n个点的树的1号结点上,每个结点上都有一个妹子。mhy从自己家出发,去给每一个妹子都送一台电脑,每个妹子拿到电脑后就会开始安装zhx牌杀毒软件,第i个妹子安装时间为Ci。树上的每条边mhy能且仅能走两次,每次耗费1单位时间。mhy送完所有电脑后会回自己家里......
  • 初中英语优秀范文100篇-017A Special Farmily Member-一位特殊的家庭成员
    PDF格式公众号回复关键字:SHCZFW017记忆树1Ben,acutedog,isaspecialmemberinmyfamily.翻译本,一只可爱的狗狗,是我家的特别成员。简化记忆狗狗句子结构这个句子的结构可以进行详细分析如下:主语:Ben,acutedog(Ben,一只可爱的狗)谓语动词:is(是)宾语:aspecial......
  • 解决:Expected 1 line break before closing bracket, but no line breaks found.eslin
    运行时报错以下 解决在eslintrc.jsrules下添加以下代码'vue/singleline-html-element-content-newline':'off','vue/multiline-html-element-content-newline':'off', ......
  • 2023版IDEA或PyCharm关闭时卡在Closing project
    当关闭IDEA或PyCharm时,提示“Closingproject”,并卡住很久。 原因之一:当项目的依赖文件没有下载或加载完成时,就会触发Closingproject。 方法一:菜单->File->Setting->Appearance&Behavior->SystemSettings->HTTPProxy->勾选“Manualproxyconfiguration......
  • Farm Chick Orgy
    Thefarmchickencarnivalbegins!Youhavetoclickonyourarrowsinvariousdirectionstomovetheeggsandcombinethemwiththenesttopassthelevel.Useyourbrainandlet'swinthecarnival.Ifyouhaveanyquestionsorsuggestionsaboutus,p......
  • TS 踩坑笔记: 箭头函数添加泛型报错(Error: JSX element ‘T’ has no corresponding
    前言今天给大家分享一个在React项目中使用TypeScript遇到的错误项目背景React+TS的项目配置,项目中关于React组件的使用.tsx后缀,其他单纯的文件使用.ts后缀问题描述在React组件附近定义泛型的箭头函数时产生TS报错警告,原本以为是语法写错了但是实际上在.t......
  • 风电分布式并网模型 Wind Farm Simulation Model。 Matlab/simulink
    风电分布式并网模型WindFarmSimulationModel。Matlab/simulink1、共2个火电厂,4个风电场,共15个节点。火电厂:1号火电厂,设定为SwingBus;2号火电厂,设定为PVBus。(在汽轮机调节器可进行调节励磁系统的控制方式)风电厂:4个风电厂;各个风电厂的风速可......
  • golang查询数据报错:closing bad idle connection: unexpected read from socket
    原因应用程序在使用驱动的有效空闲连接时候,发现数据库的连接已经失效(因为连接超过wait_timeout时间),用一个失效的连接查数据,所以报错。解决办法将sql驱动SetConnMaxLifetime和SetConnMaxIdleTime设置时间,并且小于数据库的wait_timeout时间(单位秒)。调小wait_timeout。分析......